Maximum Sub-Sequence Sum in Array (Dynamic Programming)

Problem Statement:

Suppose you have a given a integer array a[1..n]. You have to find the maximum sub sequence sum i.e. the sum of the numbers should be greater than any other sequence.

Suppose you have given an following array:

-2

-3

4

-1

-2

1

5

-3

You need to find the maximum subsequence?

We as normal human tendency always try to discard the negative number in sequence. So most of us will go with the solution 1,5 = 6 is sum of maximum sub sequence.

But that solution is wrong as the maximum sub sequence has sum 7.If you already chosen the best solution than it is great :).

Let try to search once again for the best solution without seeing below ;).

So Solution is 4, -1, -2 , 1,  5. Sum is 7.

So now we have to implement this solution by programming. We will discuss the various approach and then will try our solution with dynamic programming.

Solution Approach:

Brute Force Approach:
In brute force approach we will solve the problem in O(n) Complexity. In this approach we will iterate over each element and start doing sum until the length of array and after adding each element check sum if it is greater than max sum then replace the max sum with new value.

Note: This algorithm is implemented in this way that we always focus that sum cannot be less than zero.

Following is example

Max sum = 0;
sum = 0;

i = 0(-2)
sum = sum + (-2);
sum = -2.
So sum is less than zero so discard this sum and initialize the sum with zero.
i=1(-3)
sum = -3;
So sum is less than zero so discard this sum and initialize the sum with zero.
i=2(4)
sum = 4; 

So sum is greater than zero and max sum. So replace the max sum with sum and keep the sum.

i=3(-1)
sum = 3

So sum is greater than zero but not greater than max sum. So keep the sum but not replace with max sum.

i=4 (-2)

sum = 1

So sum is greater than zero but not greater than max sum. So keep the sum but not replace with max sum.
i=5(1)

sum = 2

So sum is greater than zero but not greater than max sum. So keep the sum but not replace with max sum.
i=6(5)
sum = 7
So sum is greater than zero and max sum(4). So replace the max sum with sum and keep the sum.
i=7(-3)

sum = 4

So sum is greater than zero but not greater than max sum. So keep the sum but not replace with max sum.
So in the end we have 7 in max sum this is our solution. We solve the problem in linear time.
The solution we provide here is according to well known Kadane's algorithm.

Dynamic Approach:

Dynamic programming solution is similar to Kadane's algorithm. We already know to solve any problem with dynamic programming it must have to attributes.

Optimal Substructure: We can solve the problem of length n by solving the lower problem. If we know the solution for i then for i+1 following will be the solution:
max(solution[i]+a[i+1],  a[i+1]);
solution[i] denotes maximum sub sequence sum for ith element.

But in this case storing solution[i] is an over head. We can simple solve the problem in linear time with time complexity O(N) and space complexity with O(1). But our topic is dynamic programming we are providing solution through dynamic approach.

Solution
Running Time : O(N)
Space Complexity: O(N)

Solution:

int calculateMaximumSubSequence(int array[], int size){

    int max[size]; // Store max sub sequence at each index. We do not need this as Kadan's algo but for dynamic approch we are using that

    memset(max, 0, size);

    int maximumSubsequence = 0; // Store max sub sequence for array

    max[0] = array[0];

    for(int i = 1; i < size;i++){

        // Check if previous max sib sequence is greater than zero. If it is negative then our condition solution[i]+a[i+1] is always less than a[i+1]

        if(max[i - 1] > 0){

            max[i] = max[i-1]+array[i];

        }else{

            max[i] = array[i];

        }

        // Store the max sub sequence for array

        if(maximumSubsequence < max[i]){

            maximumSubsequence = max[i];

        }

    }

    return maximumSubsequence;

}

You can download full source code from the link:
Please provide your input and suggestion on the tutorial.