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**.

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

add trie problems and give a separate section for multithreading.