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-

//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;
}
}

‘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-

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];
}

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

One comment on “Largest Sum Contiguous Subarray

  1. Ashutosh Jha on said:

    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

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

*

* Copy This Password *

* Type Or Paste Password Here *

43,743 Spam Comments Blocked so far by Spam Free Wordpress

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>