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 special type of dynamic programming problem. The problem is as follows:

Given an integer array nums, find the subarray with the largest sum and return its sum. The function signature is:

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.

Actually, when I first saw this problem, my initial thought was the sliding window algorithm. As we discussed in previous articles, the sliding window algorithm is specifically designed for substring/subarray problems, and this is clearly a subarray problem, right?

In the previous article Sliding Window Algorithm Framework Explained, we mentioned that to use the sliding window algorithm, you should ask yourself a few questions:

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 used for this problem because, under the condition of including negative numbers in the sum of nums, it seemed impossible to determine when to expand or shrink the window (similar to Problem 560 explained in Prefix Sum Exercises). However, inspired by reader comments, I realized that this problem can indeed be solved using the sliding window technique, though some cases are quite intricate and not easy to think of.

Therefore, I believe the sliding window solution can be considered as an extension of thinking. For similar problems, it's still better to approach them with dynamic programming/prefix sum techniques, as these methods allow for more template-based problem-solving. Below, I will explain these three solutions in turn.