Max Contigous subsequence sum

Given n numbers, find out i and j where 1<=i<=j<=n, where the sumof elements from i to j is maximum.


All positive : Sum of all elements.

All Negative : Minimum of all the values.

Solution : S(i)= Max {S(i-1)+A[i],A[i]}


Idea is to find the window that gives the maximum sum. We check
1.if previous sum + A[i] is more than A[i], if we so we add A[i]
2.Otherwise, we start from a[i] a new windows.

Eg: -2,-3,5,-1,-2,6,-3

S(1)=A[i] = -2
S(2)= Max{S(2-1)+A[2],A[2]}= Max{-2+-3,-3}=-3
S(3)= Max{S(3-1)+A[3],A[3]}= Max{-3+5,5}=5
S(4)= Max{S(4-1)+A[4],A[4]}= Max{5+-1,-1}=4  //We add -1 to +ve no expecting some +ve number in future
S(5)= Max{S(5-1)+A[5],A[5]}= Max{4+-2,-2}=2
S(6)= Max{S(6-1)+A[6],A[6]}= Max{2+6,6}=8
S(7)= Max{S(7-1)+A[7],A[7]}= Max{8+-3,-3}=5

Now loop through S[i] and return the max value, which is 8.

void maxSumsubSeq(int A[],int n)
{
int S[n];
S[0]= A[0];
int l=0;
int h=0;
for(int i=1;i<n;i++)
{
    if(S[i-1]+A[i]>A[i])
    {
        S[i]=S[i-1]+A[i];
        h=i;
    }
    else
    {
        S[i]=A[i];   //Start the window from current postion
        l=i;
        h=i;
    }
}
int max =0;
for(int i=0;i<n;i++)
{
if(S[i]>max)
max=S[i];
}