Program to find maximum contiguous subsequence sum in an array.

Solution #1: The trivial case is when all the elements in the array are positive as in that case the maximum contiguous sum is the sum of all the elements in the array. Also, when all the elements are negative, the maximum contiguous sum is 0. The below code is based on the following observations:

- A maximum contiguous subsequence(MCSS) cannot have negative elements at the boundaries.
- All subsequences that border the MCSS will have negative or zero sum otherwise they would have been a part of MCSS.

Here is the code. The complexity is O(n).

#include 
#include 

#define SIZE 10

int maxSubSum(int *A, int size)
{
    int max = 0;
    int curSum = 0;
    int i, j;

    for(i=0, j=0; j < size; j++)
    {
        curSum += A[j];

        if(curSum > max)
            max = curSum;
        else if(curSum < 0)
        {
            i = j+1;
            curSum = 0;
        }
    }

    return max;
}

int main()
{
    int A[SIZE] = {-3, 4, 2, 1, -8, -6, 4, 5, -2, -4};

    printf("Maximum contiguous subsequence sum = %d\n", maxSubSum(A, SIZE));
    return 0;
}