6-103-(LeetCode-53) 最大子序和
1. 题目
读题
https://leetcode.cn/problems/maximum-subarray/
考查点
这道题的考查点是：
- 贪心算法：贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。贪心算法在有最优子结构的问题中尤其有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。这种问题一般没有多种可能的答案。
- 动态规划：动态规划是一种将复杂问题分解成更小的子问题来解决的优化技术。动态规划和分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。换句话说，各子问题包含公共的子子问题。为了避免重复计算这些公共子子问题，我们可以用一个表来记录所有已经求过的子问题的解。
- 分治法：分治法是一种将一个复杂的问题分成两个或更多相对简单的子问题来求解的方法。分治法所能解决的问题一般具有以下几个特征：1) 该问题的规模缩小到一定的程度就可以容易地解决；2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；3) 利用该问题分解出的子问题的解可以合并为该问题的解；4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
2. 解法
思路
当然可以。这个算法的思路是这样的：
- 我们用一个变量 maxSum 来记录最大子数组和，初始值为数组的第一个元素
- 我们用另一个变量 curSum 来记录当前子数组和，初始值为 0
- 我们从左到右遍历数组中的每个元素 num
- 对于每个元素 num，我们有两种选择：要么将它加入当前子数组，要么将它作为新的子数组的起点
- 我们根据当前和 curSum 的正负来决定如何选择
- 如果 curSum 是负数，说明之前的子数组对于增大和没有帮助，所以我们舍弃它，将 curSum 重置为 num
- 如果 curSum 是非负数，说明之前的子数组对于增大和有帮助，所以我们保留它，将 curSum 增加 num
- 每次更新 curSum 后，我们都要比较它和 maxSum 的大小，如果 curSum 大于 maxSum，就将 maxSum 更新为 curSum
- 遍历完数组后，maxSum 就是最大子数组和，返回它即可
这个算法的核心思想是：只要当前和是正数，就有可能得到更大的和，所以我们尽可能地延长当前子数组；如果当前和是负数，就没有可能得到更大的和，所以我们重新开始一个新的子数组。这样，我们就能找到最大子数组和。
拓展：另外这道题还可以使用动态规划实现
具体实现
这个算法的时间复杂度是 O(n)，空间复杂度是 O(1)。
public int maxSubArray(int[] nums) {
// 初始化最大和为第一个元素
int maxSum = nums[0];
// 初始化当前和为 0
int curSum = 0;
// 遍历数组中的每个元素
for (int num : nums) {
// 如果当前和小于 0，就舍弃之前的子数组，从当前元素开始
if (curSum < 0) {
curSum = num;
} else {
// 否则，就将当前元素加到当前和中
curSum += num;
}
// 更新最大和
maxSum = Math.max(maxSum, curSum);
}
// 返回最大和
return maxSum;
}