DP Design: Maximum Subarray

LeetCode Problem 53 Maximum Subarray is very similar to the previously discussed Classic Dynamic Programming: Longest Increasing Subsequence. It represents a particular type of dynamic programming problem. The problem is as follows:

You are given an integer array nums. Find the contiguous subarray with the largest sum and return its sum. The function signature is as follows:

int maxSubArray(int[] nums);

int maxSubArray(vector<int>& nums);

def maxSubArray(nums: List[int]) -> int:

func maxSubArray(nums []int) int

var maxSubArray = function(nums) {}

For example, given the input nums = [-3,1,3,-1,2,-4,2], the algorithm returns 5, because the maximum subarray [1,3,-1,2] has a sum of 5.

When I first encountered this problem, I initially thought of the sliding window algorithm, as it is specifically designed to handle substring/subarray problems. Isn't this just a subarray problem?

In the previous article Detailed Explanation of Sliding Window Algorithm, we discussed that when using the sliding window algorithm, you should first ask yourself:

1. When should you expand the window?

2. When should you shrink the window?

3. When should you update the answer?

I previously thought that the sliding window algorithm couldn't be applied to this problem, because when summing nums with negative numbers, it seems impossible to determine when to expand or shrink the window (similar to problem 560 in the Prefix Sum Exercises). However, inspired by readers' comments, I realized that this problem can indeed be solved using the sliding window technique, although some cases are quite intricate and not easy to think of.

Therefore, I believe the sliding window solution can serve as a way to broaden your thinking. When actually encountering similar problems, it is still easier to solve them using dynamic programming/prefix sum approaches, following a more template-like thinking process. Below, I will explain these three solutions one by one.