Dynamic Programming - Maximum Subarray Sum

Given an array S of length n and integer values, we want to find the maximum subarray sum in S. For example, if S = [1, -2, 3, 4, 5, -6], the maximum subarray sum is 3+4+5=12.

Approach

To solve this problem with a Dynamic Programming approach, we need to consider whether we can use solutions to subproblems to help us in the main problem.

Define Sum(i) as the maximum subarray sum we can get at index i. In a sense, Sum(i) is the maximum sum we can get from a subarray ending at i. That way we can use this solution to bigger problems. It is worth noting that this solution is just a number, the maximum sum. If we want to know the subarray too, we would need to extend the solution. (In this example we will not implement the algorithm this way.)

Say we want to compute the solution to the problem of length n. Let Sum(n-1) be the maximum sum ending with S[n-1]. We know we must pick S[n], so the question is whether we should add Sum(n-1) to the solution or not. Remember, we want to find the maximum subarray sum, so naturally we will pick the max of the two choices. If S[n] > Sum(n-1) + S[n] then we only need to pick S[n] and leave Sum(n-1) out of the solution. Sum(n) therefore is Sum(n) = Max{Sum(n-1) + S[n], S[n]}

Generalizing, if we want to solve for length i, we have:

Sum(i) = Max{ Sum(i-1) + S[i], S[i] }

Where we are basically either choosing to pick S[i] alone or choosing to pick the solution that came before it too.

To do this, we will loop through the array S and update the values in the array of solutions.

Implementation

(Using Python)

Our given array S. This array holds any numbers, in this case positive and negative integers.

S = [-2, 1, -3, 7, -2, 3, 1, -5, 4];

The length of S.

n = len(S);

The array to hold the solutions.

sums = [0 for x in range(n+1)];

The function to calculate the solution for n will be called CalculateSubarraySum.

To iterate through the elements is S we employ the below loop. Inside this loop we will calculate the value of sums[i].

for i in range(1, n+1):
	#Here goes the code to calculate sums[i]

Remember, sums[i] should have the value of the max between sums[n-1] + S[n] and S[n]. So the loop becomes:

for i in range(1, n+1):
    if(sums[i-1] + S[i-1] > S[i-1]):
        #We pick the previous sum, plus S[i]
        sums[i] = sums[i-1] + S[i-1];
    else:
        #We pick S[i]
        sums[i] = S[i-1];

Now the array sums holds the solutions for all length from 0 to n. We need to pick and return the maximum in sums, which will also be the optimal solution for our problem.

return max(sums)

The function in its entirety:

def CalculateSubarraySum(n):
    for i in range(1, n+1):
        if(sums[i-1] + S[i-1] > S[i-1]):
            #We pick the previous sum, plus S[i]
            sums[i] = sums[i-1] + S[i-1];
        else:
            #We pick S[i]
            sums[i] = S[i-1];

    return max(sums);

To print this value, we call CalculateSubarraySum(n) and print it.

print(CalculateSubarraySum(n));

With that we are done. You can find the complete code on my Github repository.

Thanks for reading!