DP Design: Maximum Subarray
This article will resolve
LeetCode | Difficulty |
---|---|
53. Maximum Subarray | 🟠 |
Prerequisite Knowledge
Before reading this article, you need to study:
LeetCode Problem 53 "Maximum Subarray" is very similar to the problem Classic Dynamic Programming: Longest Increasing Subsequence we discussed before. This represents a common idea for some special dynamic programming problems. Here is the problem:
You are given an integer array nums
. Find the subarray with the largest sum and return the 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, if the input is nums = [-3,1,3,-1,2,-4,2]
, the algorithm returns 5, because the subarray [1,3,-1,2]
has the largest sum, which is 5.
When I first saw this problem, I thought about the sliding window algorithm, because sliding window is often used for substring or subarray problems. Isn't this a subarray problem?
In the article Sliding Window Algorithm Explained, we said you should ask yourself a few questions when you want to use the sliding window algorithm:
- When should you expand the window?
- When should you shrink the window?
- When should you update the answer?
I used to think that the sliding window could not solve this problem. The reason is that, with negative numbers in nums
, it is hard to decide when to expand or shrink the window (similar to Problem 560 discussed in Prefix Sum Exercises). But after reading some comments, I found out that it is possible to use sliding window techniques here, although some cases are a bit tricky and hard to think of.
So I think the sliding window method can be used as an extra idea. But when you see similar problems, it is easier to use dynamic programming or prefix sum techniques. These are more template-based and easier to apply. Next, I will explain all three solutions one by one.