Largest Sum Contiguous Subarray

We have a sequence of integers and we need the maximum sum from the continuous sub-sequences.

Example-

Let the sequence of integers be (3,-4,5,-7,8,-6,21,-14,-9,19).
Then,the sub-array or sub-sequence with maximum sum is (8,-6,21) and the maximum sum is 23.

Brute Force-

We can check sums of all sequences of different sizes from 1 to N.Its complexity will be O(N^2).

Code-
[cpp]
//arr[1…N] contains the given integers
for(i=1;i<N;i++)
{
s=0;
for(j=i;j<N;j++)
{
s=s+arr[j];
if(s>max) max=s;
}
}
[/cpp]
‘max’ gives the value of the maximum sum.

Efficient code-

Formulation of linear recurrence-

Let S[i] be the maximum sum of a sequence that starts with any index and ends at i.
Then,

S[i] = max (S[i-1]+arr[i],arr[i]);

Maximum of all the values of S[1…N] gives the value of the maximum sum from the continuous sub-sequences.

Example-

arr[]={2,3,-4,5}
S[1]=2;
S[2]=max(S[1]+arr[2],arr[2])=5
S[3]=max(S[2]+arr[3],arr[3])=1
S[4]=max(S[3]+arr[4],arr[4])=6

Thus,the result is max of (S[1],S[2],S[3],S[4]) which is 6.

Its time complexity is O(N).

Code-

[cpp]
S[1]=arr[1];
result=S[1];
for(i=2;i<=N;i++)
{
S[i]=std::max( S[i-1]+arr[i], arr[i] );
if(S[i]>result) result=S[i];
}
[/cpp]

NOTE– This algorithm is similar to Kadane’s algorithm.

1 Comment

  1. Very simple and elegant substitute for kadane’s. Posts are really good. Please also
    add trie problems and give a separate section for multithreading.

Leave a Reply to Ashutosh Jha Cancel reply

Your email address will not be published. Required fields are marked *