Maximum Sum Contiguous Subsequence | Dynamic Programming Set 3

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;
}

Site Footer