> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/9.dynamic-programming/53.-maximum-subarray-e.md).
# 53. Maximum Subarray (E)
Given an integer array `nums`, find the contiguous subarray (containing at least one number) which has the largest sum and return *its sum*.
A **subarray** is a **contiguous** part of an array.
**Example 1:**
```
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
```
**Example 2:**
```
Input: nums = [1]
Output: 1
```
**Example 3:**
```
Input: nums = [5,4,-1,7,8]
Output: 23
```
**Constraints:**
* `1 <= nums.length <= 105`
* `-104 <= nums[i] <= 104`
**Follow up:** If you have figured out the `O(n)` solution, try coding another solution using the **divide and conquer** approach, which is more subtle.
### Solution:
**Version 1: DP:**
其实第一次看到这道题，我首先想到的是 [滑动窗口算法](https://labuladong.github.io/algo/2/21/60/)，因为我们前文说过嘛，滑动窗口算法就是专门处理子串/子数组问题的，这里不就是子数组问题么？
但是，稍加分析就发现，**这道题还不能用滑动窗口算法，因为数组中的数字可以是负数**。
滑动窗口算法无非就是双指针形成的窗口扫描整个数组/子串，但关键是，你得清楚地知道什么时候应该移动右侧指针来扩大窗口，什么时候移动左侧指针来减小窗口。
而对于这道题目，你想想，当窗口扩大的时候可能遇到负数，窗口中的值也就可能增加也可能减少，这种情况下不知道什么时机去收缩左侧窗口，也就无法求出「最大子数组和」。
解决这个问题需要动态规划技巧，但是 `dp` 数组的定义比较特殊。按照我们常规的动态规划思路，一般是这样定义 `dp` 数组：
**`nums[0..i]` 中的「最大的子数组和」为 `dp[i]`**。
如果这样定义的话，整个 `nums` 数组的「最大子数组和」就是 `dp[n-1]`。如何找状态转移方程呢？按照数学归纳法，假设我们知道了 `dp[i-1]`，如何推导出 `dp[i]` 呢？
如下图，按照我们刚才对 `dp` 数组的定义，`dp[i] = 5` ，也就是等于 `nums[0..i]` 中的最大子数组和：
[](https://labuladong.github.io/algo/images/%e6%9c%80%e5%a4%a7%e5%ad%90%e6%95%b0%e7%bb%84/1.jpeg)
那么在上图这种情况中，利用数学归纳法，你能用 `dp[i]` 推出 `dp[i+1]` 吗？
**实际上是不行的，因为子数组一定是连续的，按照我们当前 `dp` 数组定义，并不能保证 `nums[0..i]` 中的最大子数组与 `nums[i+1]` 是相邻的**，也就没办法从 `dp[i]` 推导出 `dp[i+1]`。
所以说我们这样定义 `dp` 数组是不正确的，无法得到合适的状态转移方程。对于这类子数组问题，我们就要重新定义 `dp` 数组的含义：
**以 `nums[i]` 为结尾的「最大子数组和」为 `dp[i]`**。
这种定义之下，想得到整个 `nums` 数组的「最大子数组和」，不能直接返回 `dp[n-1]`，而需要遍历整个 `dp` 数组：
```java
int res = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
res = Math.max(res, dp[i]);
}
return res;
```
依然使用数学归纳法来找状态转移关系：假设我们已经算出了 `dp[i-1]`，如何推导出 `dp[i]` 呢？
可以做到，`dp[i]` 有两种「选择」，要么与前面的相邻子数组连接，形成一个和更大的子数组；要么不与前面的子数组连接，自成一派，自己作为一个子数组。
如何选择？既然要求「最大子数组和」，当然选择结果更大的那个啦：
```java
// 要么自成一派，要么和前面的子数组合并
dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
```
综上，我们已经写出了状态转移方程，就可以直接写出解法了：
```java
int maxSubArray(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
// 定义：dp[i] 记录以 nums[i] 为结尾的「最大子数组和」
int[] dp = new int[n];
// base case
// 第一个元素前面没有子数组
dp[0] = nums[0];
// 状态转移方程
for (int i = 1; i < n; i++) {
dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
}
// 得到 nums 的最大子数组
int res = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
res = Math.max(res, dp[i]);
}
return res;
}
```
以上解法时间复杂度是 O(N)，空间复杂度也是 O(N)，较暴力解法已经很优秀了，不过**注意到 `dp[i]` 仅仅和 `dp[i-1]` 的状态有关**，那么我们可以施展前文 [动态规划的降维打击](https://labuladong.github.io/algo/3/23/75/) 讲的技巧进行进一步优化，将空间复杂度降低：
```java
int maxSubArray(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
// base case
int dp_0 = nums[0];
int dp_1 = 0, res = dp_0;
for (int i = 1; i < n; i++) {
// dp[i] = max(nums[i], nums[i] + dp[i-1])
dp_1 = Math.max(nums[i], nums[i] + dp_0);
dp_0 = dp_1;
// 顺便计算最大的结果
res = Math.max(res, dp_1);
}
return res;
}
```
#### 最后总结
虽然说动态规划推状态转移方程确实比较玄学，但大部分还是有些规律可循的。
今天这道「最大子数组和」就和「最长递增子序列」非常类似，`dp` 数组的定义是「以 `nums[i]` 为结尾的最大子数组和/最长递增子序列为 `dp[i]`」。因为只有这样定义才能将 `dp[i+1]` 和 `dp[i]` 建立起联系，利用数学归纳法写出状态转移方程。
**Version 2: Greedy**
```
public class Solution {
public int maxSubArray(int[] A) {
if (A == null || A.length == 0){
return 0;
}
//max记录全局最大值，sum记录区间和，如果当前sum>0，那么可以继续和后面的数求和，否则就从0开始
int max = Integer.MIN_VALUE, sum = 0;
for (int i = 0; i < A.length; i++) {
sum += A[i];
max = Math.max(max, sum);
sum = Math.max(sum, 0);
}
return max;
}
}
```
**Version 3: Prefix Sum**
```
public class Solution {
public int maxSubArray(int[] A) {
if (A == null || A.length == 0){
return 0;
}
//max记录全局最大值，sum记录前i个数的和，minSum记录前i个数中0-k的最小值
int max = Integer.MIN_VALUE, sum = 0, minSum = 0;
for (int i = 0; i < A.length; i++) {
sum += A[i];
max = Math.max(max, sum - minSum);
minSum = Math.min(minSum, sum);
}
return max;
}
}
```
---
# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.
## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://junnie.gitbook.io/nine-chapter/9.dynamic-programming/53.-maximum-subarray-e.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.