Maximum Subarray

Today we take a look at Maximum Subarray Though problem is a common problem asked during interviews and has a straight forward answer, many struggle on the what the dynamic programming table should keep track of -so it’s worth doing a deeper study of the problem.

The intuition behind the solution relies on three facts.

Fact 1: We don’t need to keep track of the actual subarray that will give us the maximum sub, we just need to know the max sum. This is important.

Fact 2: If the input contained all positive numbers, the max subarray would be the entire array. Negative values in the array cause the subarray to be less than the full input. This is important to the intuition behind the solution. As we traverse the array, at each position, i, we want to see if we should include it in the previous subarray or create a new subarray starting at i.

Fact 3: Continuing from fact 2, given such a number nums[i+1], we can decide if it should be included in the existing subarray or become the start of a new subarray by seeing sum([nums[j], nums[j+1], ... nums[i], nums[i+1]]) is less than nums[i+1]. If nums[i+1] is grater than the sums, it means that existing subarray carries a negative value or both the sum and nums[i+1] are negative. In either case, it makes sense to start a new subarray starting at index i+1 since including it in the previous subarray would yield a lower sum value.

And this gives us the intuition behind the solution. Start at index 0 and traverse though the array keeping track of a running total for each nums[i] in a separate array. Let’s call this separate array memo. If at some point we see a nums[i] such that: nums[i] > sum[num[j]..num[i-1], nums[i]) then, we set memo[i] to nums[i] and keep going. It’s important to note that memo[n] does does not mean the actual subarray is nums[0] to nums[n]. The actual subarray may be any subset from nums[0] to nums[n], such as 4 to n or even just nums[n] itself.

After we have traversed though the entire input, we simply iterate though the memo array and return the maximum value found.

Optimal Substructure – This exists because if we find the optimal solution for inputs nums[0...n], we can use it’s solution to find the optimal solution for inputs nums[0..., n, n+1].

Overlapping Sub-problem – This exists because we need to calculate largest sum of any contiguous subarray for each number in the input. For each number, n, as we carry out the calculation, we require the solution for the subproblem on index n-1 (and so on).

Base case – By definition, our base case is memo[0] = nums[0].

DP Table

Our solution relies on the “memo” array described in fact 3. At any position n, this array contains the largest sum of any contiguous subarray (either ending at n or just n itself) from in nums[0…n].

    public int maxSubArray(int[] nums) {
     
        int[] memo = new int[nums.length];
        memo[0] = nums[0];
        
        int maxFound = memo[0];        
        
        if (nums == null) {
            return 0;
        } else if (nums.length == 1){
            return nums[0];      
        }

        for(int i=1;i<nums.length; i++){
            
            int currentNum = nums[i];        
            memo[i] = Math.max(currentNum, memo[i-1]+currentNum);
            maxFound = maxFound < memo[i] ? memo[i] : maxFound;
        }
        
        return maxFound;
    }