难度: Easy
某公司每日销售额记于整数数组 sales，请返回所有 连续 一或多天销售额总和的最大值。
要求实现时间复杂度为 O(n) 的算法。
示例 1:
输入：sales = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：[4,-1,2,1] 此连续四天的销售总额最高，为 6。
示例 2:
输入：sales = [5,4,-1,7,8] 输出：23 解释：[5,4,-1,7,8] 此连续五天的销售总额最高，为 23。
提示：
1 <= arr.length <= 10^5-100 <= arr[i] <= 100注意：本题与主站 53 题相同：https://leetcode-cn.com/problems/maximum-subarray/
运行时间: 64 ms
内存: 18.4 MB
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
max_sum = float("-inf")
cur_sum = 0
for num in nums:
cur_sum += num
max_sum = max(cur_sum, max_sum)
cur_sum = max(cur_sum, 0)
return max_sum
题解采用了'Kadane算法'，用以解决最大子数组和的问题。首先初始化最大和max_sum为负无穷，当前和cur_sum为0。遍历数组中的每个元素，将当前元素累加到cur_sum上。如果cur_sum更新后的值比max_sum大，则更新max_sum。之后，如果cur_sum小于0，将其重置为0，因为任何负的当前和都不会对找到一个更大的子数组和有帮助。这样，通过一次遍历数组，就能得到最大的子数组和。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
max_sum = float('-inf') # 初始化最大子数组和为负无穷大
cur_sum = 0 # 当前子数组的和
for num in nums: # 遍历数组中的每个元素
cur_sum += num # 更新当前子数组的和
max_sum = max(cur_sum, max_sum) # 更新最大子数组和
cur_sum = max(cur_sum, 0) # 如果当前和小于0，重置为0
return max_sum # 返回最大子数组和
在Kadane算法中，如果当前和cur_sum小于0，意味着加上当前子数组的和会让整体和更小，这对寻找最大子数组和是不利的。因此，将cur_sum重置为0是为了舍弃当前的负累积和，从下一个元素重新开始计算新的子数组和，以寻找可能存在的更大的子数组和。这种做法确保了算法总是尝试捕捉到最有利的起点，从而最大化整体的子数组和。
Kadane算法能够处理所有元素都是负数的情况。即使所有元素都是负数，算法仍会通过遍历每个元素来更新最大子数组和max_sum。在这种情况下，最大子数组和将是数组中单个最小负值（即绝对值最小的负数），因为任何负数相加都会产生更小的和。因此，即使所有数都为负，Kadane算法仍然能找到最大子数组和，即这些负数中的最大值。
在Kadane算法中，如果数组包含0或正负相间的数，算法仍然有效。0的存在不会对当前和产生负面影响，但也不增加和；在计算过程中，0可以作为连接正数的桥梁，有助于维持当前和。正负相间的数会使得当前和经常重置，但Kadane算法通过不断比较和更新最大子数组和max_sum，能够有效地处理这种波动，最终找到最优的子数组和。
在实现Kadane算法时，初始化max_sum为负无穷大是为了确保算法能够正确处理所有元素都是负数的情况。如果初始化为0，在全是负数的数组中，算法将错误地返回0作为最大子数组和，这是不正确的，因为最大子数组和应该是数组中的最大负数。初始化为负无穷大确保了无论数组内容如何，max_sum总能被数组中的任何值（包括负数）更新。