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

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

add trie problems and give a separate section for multithreading.