Maximum Subarray
你会得到一个整数列表 nums。子数组是由连续相邻元素组成的一段序列，中间不能有间隔，而且至少要包含一个元素。请返回 nums 中任意子数组可能得到的最大和。你只需返回这个和，不需要返回子数组本身。
函数
- numsinteger-array
- 整数列表，且至少包含一个元素
- 返回值integer
- 一段非空相邻元素序列的最大和
约束条件
1 ≤ nums.length ≤ 105-104 ≤ nums[i] ≤ 104- 答案始终可以用 32 位有符号整数表示。
示例
- 输入
- nums = [2, -4, 3, -1, 5, -6, 1]
- 输出
- 7
- 解释
- 序列
[3, -1, 5]的总和是 7。向左延伸会加上 -4，然后加上 2，净损失为 2。向右延伸会加上 -6，然后加上 1，净损失为 5。没有其他序列能取得更好的结果。
- 输入
- nums = [-3, -1, -2]
- 输出
- -1
- 解释
- 所有数字都是负数，所以连续子数组越长，和就越小。最优的连续子数组只有一个元素 -1。子数组不能为空，因此答案是 -1，而不是 0。
进阶
你也能用分治法在 O(n log n) 时间内解决这个问题吗？把列表分成两半，并处理跨越中间位置的连续段。
提示
逐个打开提示，每个都会多透露一点。
关注恰好在某个位置结束的连续段。这里结束的最佳连续段，与紧邻它前一个位置结束的最佳连续段有什么关系？
在当前元素处结束的连续段，要么延续紧邻它之前结束的连续段，要么从当前元素重新开始。只有当之前的连续段总和为正数时，延续它才有帮助。
遍历列表一次，并记录两个数：以当前元素结尾的一段连续元素的最大和，以及目前为止找到的最大和。将两者都初始化为第一个元素，这样即使列表中的数全是负数，也会返回其中最大的数。
题解
含有 n 个数字的列表大约有 n²/2 个子数组，对于 10^5 个元素来说，逐个检查太多了。难点在于负数：如果后面的元素能弥补负数带来的影响，就应该在连续片段中保留这个负数；否则，就丢弃它之前的所有内容。Kadane 算法会在每个元素处通过一次比较做出这个选择。
对每个子数组求和
结果正确，但无法在最大的测试中运行完毕
思路
每个子数组都有一个起始索引 left 和一个结束索引 right，所以尝试每一对索引就能找到最优解。固定 left，向前移动 right，并将每个新元素加到运行中的 total：每个子数组只需进行一次加法，不需要第三层循环。
但这样仍有大约 n²/2 对索引，对于 10^5 个元素来说，需要进行 50 亿次加法。
算法
- 将
best设为第一个元素。 - 对于每个起始索引
left，将累加用的total设为 0。 - 让
right从left移动到列表末尾，并将nums[right]加到total中。 - 每次加法后，如果
total更大，就将它存入best。 - 返回
best。
def maxSubArray(nums):
best = nums[0]
for left in range(len(nums)):
total = 0
# Grow the subarray that starts at left by one element at a time
for right in range(left, len(nums)):
total += nums[right]
best = max(best, total)
return bestKadane 算法
思路
以索引 i 结尾的最佳连续子数组，要么只有 nums[i]，要么是在以 i-1 结尾的最佳连续子数组中加上 nums[i]，因为以 i-1 结尾的其他连续子数组的和都不会更大。因此，只需保留一个数 endingHere，表示以当前元素结尾的连续子数组的最大和。到下一个元素 x 时，它会变成 x 和 endingHere + x 中较大的那个：当连续子数组的和为正数时，就继续扩展；一旦和为零或负数，就从 x 重新开始。
最大子数组会在某个位置结束，所以答案是 endingHere 所取的最大值。在第一个示例中，它依次为 2、-2、3、2、7、1、2，答案是 7。
算法
- 将
endingHere和best设为第一个元素。 - 对于后续的每个元素
x，将endingHere设为x和endingHere + x中较大的值。 - 将
best设为best和endingHere中较大的值。 - 处理完最后一个元素后，返回
best。
def maxSubArray(nums):
current = nums[0]
best = nums[0]
for i in range(1, len(nums)):
current = max(nums[i], current + nums[i])
best = max(best, current)
return best
易错点和边界情况
- 从 0 开始设置
best。[-3, -1, -2]会返回 0，而不是 -1。应从第一个元素开始。 - 用
max(0, endingHere + x)限制当前和。对于同一个列表，这种做法会出错；应改为与x比较。 - 只把正数相加。元素必须相邻，所以第一个示例的结果是 7，而不是 2 + 3 + 5 + 1 = 11。
- 从索引 1 开始循环，却没有将
endingHere和best设为nums[0]。像[-5]这样只有一个元素的列表必须返回 -5。
常见问题3
什么是 Kadane 算法？
Kadane 算法只需遍历一次，就能找出连续子数组的最大和。它会记录以当前元素结尾的一段连续子数组的最大和。遇到新元素时，它会选择延长这段子数组，或者从新元素开始计算。所有这些和中的最大值就是答案。
最大子数组的时间复杂度是多少？
Kadane 算法的时间复杂度为 O(n)，额外空间复杂度为 O(1)，因为每个元素只需查看一次。使用累计总和检查每个子数组需要 O(n²)，而从头计算每个子数组的总和需要 O(n³)。
为什么最大子数组问题属于动态规划问题？
在索引 i 处结束的连续片段的最大和，只取决于在索引 i-1 处结束的连续片段的最大和。这是在索引上进行递推，这正是动态规划的形式。Kadane 算法只保留最新的值，而不保存整张表，因此只需要 O(1) 的空间。
def maxSubArray(nums):
# 在这里编写代码测试 #1
测试 #2
参数
nums = [2, -4, 3, -1, 5, -6, 1]
预期输出
7