Given an array A having n integers. We need to give an algorithm to find a contiguous subseqnence (A[i], A[i+1], …, A[j]) such that the sum of the elements in that subsequence is maximized. (Note that, in general, there may be more than one such optimal subsequence.

Example : {2,-4,1,2} -> 1 and {1,-3,4,-2,-1,7} -> 8

Note:If there are no negative number then the solution is just the sum of all element in the array 😛

Method:1

Algorithm Paradigm : Dynamic Programming

Let MSCS[i] represents maximum sum over all the elements ending at i including A[i]

Consider the following array

------------------------------------ | | | | ? | | | | ------------------------------------ A[0] A[i]

For Finding maximum element we have to do one of the following and select max of them:

Either extend old sum with ith element A[i]

or Start with new Element starting with A[i]

i.e

MSCS[i] = Max{ MSCS[i-1] + A[i] , //extend old sum by A[i] { 0 //Start new window with A[i]

Time and Space Complexity: O(n) and O(n)

C++ implementation:

#include <iostream> #include <algorithm> using namespace std; int MaxSumContSub(int arr[],int size) { int *mscs = new int[size]; if(size == 0) return 0; mscs[0] = arr[0]; for(int i = 1; i < size ;i++) { mscs[i] = std::max((mscs[i-1]+arr[i]),0); } int max = -1; for(int i = 0;i<size;i++) { if(max < mscs[i]) { max = mscs[i]; } } return max; } int main( ) { int arr[] = {1,-3,4,-2,-1,7}; int n = sizeof(arr)/sizeof(int); cout<<"sum = "<<MaxSumContSub(arr,n); return 0; }