# 动态规划设计：最大子数组

Info

**已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~**

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode | Difficulty |
---|---|

53. Maximum Subarray | 🟠 |

Prerequisites

Before reading this article, you should learn:

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:

- When should you expand the window?
- When should you shrink the window?
- 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.