And here is our second problem of the Dynamic Programming Series! As promised, this one will be much simpler than the last one.

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4]

Output: 6

Explanation: [4,-1,2,1] has the largest sum = 6

Right off the bat, we notice similarities of this problem to the last one in that we have to consider all possible contiguous subarrays (like how we had to consider all possible substrings in the our last problem). Again, this means that a bottom-up approach would work best.

The Objective

Our goal is really simply to return the sum of a contiguous subarray with the largest sum. This means what we really care about is keeping track of the largest sums of contiguous subarrays. Using the bottom-up approach here means we need to figure out a structure of using computed solutions from our base cases to work our way up. So how can we, while iterating through the array of numbers, compute a new sum using sums that were previously computed?

sum[i+1] = function(sum[i])

Essentially, we want to figure out the function that would compute sum[i+1] as shown above given sum[i], which was previously computed. Hopefully, at this point, it is clear that this function would essentially be (where arr is our input array):

function(sum[i]) {
    if (sum[i] + arr[i+1] < sum[i]) {
        return sum[i]
    } else {
        return sum[i] + arr[i+1]
    }
}

This function will correctly return the current largest sum throughout contiguous subarrays up until index i. Now that we understand the general structure of how we want to build around our code, we are ready to initialize our tabulation and establish the base case.

Tabulation

Because we are simply tracking the largest sums of contiguous subarrays up until index n-1, where n is the length of our input array, all we need is a 1D array with length n.

# initialize the array where we store our computed solutions
max_sums = [float("-inf") for i in range(len(num_array))]

Note: we initialize the array with negative infinity as the value

Base Case

We can simply define when i = 0, so this would be:

max_sums[0] = max(float("-inf"), num_array[0])

Which can really be simplified to:

max_sums[0] = num_array[0]

Because we know that any number is > negative infinity.

Working Our Way Up

Using our insight of the general structure, we can concise this in Python into a single line with the max() function. The built-in max() function returns the maximum of the two values. Finally, we can return the maximum of sums using the max() function again. In this case, the max() functions goes through the array and returns the max value of the array.

for j in range(1, len(num_array)):
    max_sums[j] = max(max_sums[j-1] + num_array[j], num_array[j])

return max(max_sums)

Extra Challenge

And we're done! As an extra challenge I tried to use dynamic programming to find both the contiguous subarray and the sum, but failed to find a solution for that. I did find a non-DP solution for it though, which is as follows:

def function(num_array):

    max_sum = float("-inf")
    start = 0
    end = 1

    for i in range(1, len(num_array)):
        sum = 0
        for j in range(i, len(num_array)):
            sum += num_array[j]
            if sum > max_sum:
                max_sum = sum
                start = i
                end = j + 1

    print("The array " + str(num_array[start:end]) + " has the largest sum of " + str(max_sum))

Feel free to share me your solution for this extra challenge. I would love to see a different approach!

Steffy's Blog