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:

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!