Find Maximum Subarray Sum
———————-

Problem

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 the maximum in sums, which will also be the optimal solution for our problem.

#We search for the max in sums
m = sums[0]; #The max will be stored here
for i in range(1,n+1):
    if(sums[i] > m):
        m = sums[i];

The variable m now holds the maximum subarray sum. We return it and we have completed our computation 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];

    #We search for the max in sums
    m = sums[0]; #The max will be stored here
    for i in range(1,n+1):
        if(sums[i] > m):
            m = sums[i];

    return m;

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!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s