网硕互联帮助中心分析
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。
题解
朴素动态规划
核心思想：
DP 状态定义 dp[i]：以 下标 i 结尾 的连续子数组的最大和。 关键点：必须以 i 结尾，保证连续性。
状态转移方程（核心公式）
d
p
[
i
]
=
max
(
n
u
m
s
[
i
]
,
d
p
[
i
−
1
]
+
n
u
m
s
[
i
]
)
dp[i] = \\max(nums[i],\\ dp[i-1] + nums[i])
dp[i]=max(nums[i], dp[i−1]+nums[i]) 两种选择：
-
舍弃前面：子数组从当前元素重新开始，取 nums[i]
-
接上前面：把当前元素拼接到前一个最优子数组后，取 dp[i-1] + nums[i]
全局答案：遍历所有dp[i] 取最大值。
代码
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n);
dp[0] = nums[0];
int maxSum = nums[0];
for(int i = 1; i < n; i++){
dp[i] = max(nums[i], dp[i–1] + nums[i]);
maxSum = max(maxSum, dp[i]);
}
return maxSum;
}
};
时间复杂度：
O
(
n
)
O(n)
O(n) 空间复杂度：
O
(
n
)
O(n)
O(n)
最优解：Kadane 贪心 DP（空间优化）
优化思路
观察 DP 方程：dp[i] 只依赖 dp[i-1]，不需要存整个数组。
用单个变量滚动替换 dp 数组：
-
curSum：替代 dp[i]，当前结尾的最大子数组和
-
maxSum：全局最大值
代码
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int curSum = nums[0];
int maxSum = nums[0];
for(int i = 1; i < nums.size(); ++i) {
curSum = max(nums[i], curSum + nums[i]);
maxSum = max(maxSum, curSum);
}
return maxSum;
}
};
时间复杂度：
O
(
n
)
O(n)
O(n) 空间复杂度：
O
(
1
)
O(1)
O(1)
拓展解法：分治算法
分治核心思想
最大子数组只存在三种情况：
完全在左半区间
完全在右半区间
跨越中点（左后缀 + 右前缀）
递归求解左右最大值，再计算跨中点最大值，三者取最大。
代码
class Solution {
public:
int maxSubArray(vector<int>& nums) {
return divide(nums, 0, nums.size()–1);
}
int divide(vector<int>& nums, int l, int r){
if(l == r) return nums[l];
int mid = l + (r – l) / 2;
int leftMax = divide(nums, l, mid);
int rightMax = divide(nums, mid+1, r);
int crossMax = getCross(nums, l, mid, r);
return max({leftMax, rightMax, crossMax});
}
int getCross(vector<int>& nums, int l, int mid, int r){
int leftSum = 0, leftMaxSum = INT_MIN;
for(int i = mid; i >= l; i—){
leftSum += nums[i];
leftMaxSum = max(leftMaxSum, leftSum);
}
int rightSum = 0, rightMaxSum = INT_MIN;
for(int i = mid+1; i <= r; i++){
rightSum += nums[i];
rightMaxSum = max(rightMaxSum, rightSum);
}
return leftMaxSum + rightMaxSum;
}
};
补充：
c
r
o
s
s
M
a
x
=
(
max
k
∈
[
l
,
m
i
d
]
∑
i
=
k
m
i
d
n
u
m
s
[
i
]
)
+
(
max
k
∈
[
m
i
d
+
1
,
r
]
∑
i
=
m
i
d
+
1
k
n
u
m
s
[
i
]
)
crossMax = \\Bigl(\\max_{k\\in[l,mid]}\\sum_{i=k}^{mid}nums[i]\\Bigr) +\\Bigl(\\max_{k\\in[mid+1,r]}\\sum_{i=mid+1}^{k}nums[i]\\Bigr)
crossMax=(k∈[l,mid]maxi=k∑midnums[i])+(k∈[mid+1,r]maxi=mid+1∑knums[i])
- 第一部分：
[
l
,
m
i
d
]
[l,mid]
[l,mid] 内以 mid 结尾的最大后缀和 - 第二部分：
[
m
i
d
+
1
,
r
]
[mid+1,r]
[mid+1,r] 内以 mid+1 开头的最大前缀和
时间复杂度：
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn) 空间复杂度：
O
(
l
o
g
n
)
O(logn)
O(logn)，递归栈
三种算法对比总结
| 朴素 DP | O(n) | O(n) | 教学理解 |
| Kadane（优化DP） | O(n) | O(1) | 刷题、面试最优解 |
| 分治 | O(nlogn) | O(logn) | 面试拓展、思维考察 |
53. 最大子数组和 – 力扣（LeetCode）
评论前必须登录！
注册