We have a sequence of integers and we need the maximum sum from the continuous sub-sequences.
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.
We can check sums of all sequences of different sizes from 1 to N.Its complexity will be O(N^2).
//arr[1…N] contains the given integers
‘max’ gives the value of the maximum sum.
Formulation of linear recurrence-
Let S[i] be the maximum sum of a sequence that starts with any index and ends at i.
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.
Thus,the result is max of (S,S,S,S) which is 6.
Its time complexity is O(N).
S[i]=std::max( S[i-1]+arr[i], arr[i] );
NOTE– This algorithm is similar to Kadane’s algorithm.