# 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=2;
S=max(S+arr,arr)=5
S=max(S+arr,arr)=1
S=max(S+arr,arr)=6

Thus,the result is max of (S,S,S,S) which is 6.

Its time complexity is O(N).

Code-

[cpp]
S=arr;
result=S;
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. saurabh

## 1 Comment

1. Ashutosh Jha says:

Very simple and elegant substitute for kadane’s. Posts are really good. Please also