题目描述
给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。
示例 1
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6。
示例 2
输入：nums = [1]
输出：1
示例 3
输入：nums = [5,4,-1,7,8]
输出：23
核心考点
- 贪心算法的应用（局部最优推导全局最优）；
- 动态规划的状态定义与转移；
- 时间复杂度的优化（从 O(n²) 到 O(n)）。
解题思路
1. 暴力解法
遍历所有可能的连续子数组，计算每个子数组的和，记录最大值。
具体步骤：
- 外层循环控制子数组的起始位置（i 从 0 到 nums.length-1）；
- 内层循环控制子数组的结束位置（j 从 i 到 nums.length-1）；
- 在遍历过程中，累加子数组的和（从 i 到 j），并实时更新最大和；
- 遍历结束后，返回最大和。
优点：逻辑简单，容易理解。 缺点：时间复杂度 O(n²)，当数组长度较大时会超时。
2. 动态规划
动态规划的核心是'状态定义'和'状态转移方程'。
第一步：定义状态 设 dp[i] 表示'以第 i 个元素结尾的连续子数组的最大和'。
第二步：推导状态转移方程 对于第 i 个元素，有两种选择：
- 将第 i 个元素加入到以 i-1 结尾的子数组中（即 dp[i-1] + nums[i]）；
- 不加入前序子数组，单独以第 i 个元素作为新的子数组（即 nums[i]）。
取两者中的最大值： dp[i] = max(dp[i-1] + nums[i], nums[i])
第三步：初始化与结果计算
- 初始化：dp[0] = nums[0]；
- 结果：遍历 dp 数组，取其中的最大值。
优化点：不用额外开辟 dp 数组，用一个变量临时存储 dp[i-1] 的值，将空间复杂度从 O(n) 优化到 O(1)。
3. 贪心算法
贪心算法的核心是'局部最优解推导全局最优解'。当前子数组的和为负数时，放弃这个子数组，重新开始计算。
具体逻辑：
- 定义两个变量：currentSum（当前子数组的和）、maxSum（全局最大和）；
- 遍历数组，每次将当前元素加入 currentSum；
- 如果 currentSum > maxSum，更新 maxSum；
- 如果 currentSum < 0，说明当前子数组的和已经是负数，继续往后加只会更小，因此将 currentSum 重置为 0（或当前元素）；
- 遍历结束后，返回 maxSum。
注意：当数组中所有元素都是负数时，需特殊处理（如初始化为第一个元素）。
代码实现
解法 1：暴力解法（参考）
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int maxSum = nums[0];
for (int i = 0; i < n; i++) {
int currentSum = 0;
for (int j = i; j < n; j++) {
currentSum += nums[j];
if (currentSum > maxSum) {
maxSum = currentSum;
}
}
}
return maxSum;
}
}
// 时间复杂度：O(n²)，空间复杂度：O(1)
解法 2：动态规划（推荐）
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
int preSum = nums[0];
int maxSum = nums[0];
for (int i = 1; i < n; i++) {
preSum = Math.max(preSum + nums[i], nums[i]);
maxSum = Math.max(maxSum, preSum);
}
return maxSum;
}
}
// 时间复杂度：O(n)，空间复杂度：O(1)
解法 3：贪心算法（推荐）
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
int currentSum = nums[0];
int maxSum = nums[0];
for (int i = 1; i < n; i++) {
currentSum = Math.max(currentSum + nums[i], nums[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
}
// 时间复杂度：O(n)，空间复杂度：O(1)
关键细节
- 数组全为负数的情况：必须将 maxSum 初始化为 nums[0]，避免结果为 0。
- 子数组的连续性：必须是连续的，不能跳过元素。
- 贪心算法的重置时机：只有当 currentSum 为负数时，才重置为当前元素。
- 动态规划的状态定义：必须是'以第 i 个元素结尾'，否则无法保证连续性。
拓展思考
- 要求返回最大子数组的起始和结束索引；
- 最大子数组和的个数；
- 二维数组的最大子数组和。
其中，'返回最大子数组的起始和结束索引'是最常考的延伸，可基于贪心或动态规划修改代码实现。
总结
最大子数组和是贪心和动态规划的经典入门题。
- 暴力解法：效率低，适合入门；
- 动态规划：通过状态定义和转移方程，实现 O(n) 时间复杂度，空间可优化到 O(1)；
- 贪心算法：逻辑简洁，效率最高。
建议先动手写一遍暴力解法，再逐步优化，注意规避常见坑（全负数、连续性）。