Maximum Subarray, using DP

Question: Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. You may view the full question here.

Approach 2: The previous post describes a O(n) approach. But, out of curiosity, I wanted to see how a Divide-and-Conquer or a DP approach would look like. My DP skills particularly are rusty at this point in time. So, what seemed like an eternity in internet surfing time, I found this great snippet with explanation in the discussion section.

To quickly recap — Dynamic programming, a.k.a. DP is the process of solving a big complex problem by breaking it down into smaller sub problems.

So, in our case, instead of considering the whole array at a time, we build the array by adding one element at a time, starting from the element in the first position. The empirical formula for the sub-problem would look something like this —

SUM[i] = Max(SUM[i-1]+num[i], num[i])

We need to remember that SUM[i] does NOT mean the maximum sum value for the array containing the elements from the positions 0 to i.

To explain this, let’s quickly borrow the concept from the previous post. Say the maximum subarray consists of two parts — sub-subarray A and sub-subarray B. sub-subarray A is the array from the initial part of the array that consists of all the elements already encountered. And sub-subarray B of course consists of the elements that are lying on the other side, waiting to be read/evaluated.

Let’s visualize this —

A pictorial representation of the formula

The green cells are included in the sum subarray that is being constructed using the formula. Notice how the selected elements are always to the right. This is because we are aiming to construct a continuous subarray. Clearly this approach will not necessarily give us the maximum subarray. To keep track of the maximum sum so far, we need another variable/holder.

There is not much difference in the previous code and this one, except that we are maintaining a complete array that holds all the sum values encountered in each step.

//Approach 2
//Runtime: 6ms
//Memory usage: 38.6MB
class Solution {
    public int maxSubArray(int[] nums) {
        int[] sum = new int[nums.length];
        sum[0] = nums[0];
        int max = nums[0];
        for(int i=1; i<nums.length; i++){
            sum[i] = Math.max(sum[i-1]+nums[i], nums[i]);
            max = Math.max(max, sum[i]);
        }
        return max;
    }
}

Honestly, this approach seems like a step down from the previous one. But, there is no difference in the Run Time. Like I said, just wanted to dab around with DP a little. So here it is.

Find more posts here.

Cheers & Chao!