难度: Medium
给你一个整数数组 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
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 104进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
运行时间: 52 ms
内存: 15.3 MB
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
max_sum = float('-inf')
s = 0
for num in nums:
if s < 0:
s = num
else:
s += num
max_sum = max(max_sum, s)
return max_sum
这个题解使用了动态规划的思想。通过遍历数组，对于每个元素，判断将其加入当前子数组是否会使当前子数组的和增大。如果当前子数组的和小于0，那么加上当前元素会使子数组的和变小，因此将当前子数组的和重置为当前元素。否则，将当前元素加入子数组。同时，更新最大子数组和。最终返回遍历过程中得到的最大子数组和。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
max_sum = float('-inf') # 初始化最大子数组和为负无穷
s = 0 # 初始化当前子数组的和为0
for num in nums: # 遍历数组中的每个元素
if s < 0: # 如果当前子数组的和小于0
s = num # 将当前子数组的和重置为当前元素
else:
s += num # 否则，将当前元素加入子数组
max_sum = max(max_sum, s) # 更新最大子数组和
return max_sum # 返回最大子数组和
在动态规划中，如果当前子数组的和小于0，意味着它对增加未来元素的总和没有贡献，反而会减少总和。因此，最优的选择是放弃当前的子数组和，从新的元素重新开始计算子数组的和。这样可以确保子数组的最大可能和不会被一个负的子数组和所拖累。
初始化`max_sum`为负无穷大是为了确保在遍历数组的过程中，任何一个元素的值都能被考虑进最大子数组和中，即使所有元素都是负数。这种初始化方法保证了`max_sum`能够正确地更新为数组中的最大值。另一种可能的初始化方式是将`max_sum`初始化为数组中的第一个元素，但这需要额外的逻辑来确保数组不为空。
是的，题解中的动态规划解法已经考虑了所有边界情况。即使数组中所有元素都是负数，通过初始化`max_sum`为负无穷并在每个元素上更新它，可以保证找到最大的子数组和，即便这个和依然是负数。对于只包含一个元素的数组，算法会将这个单一元素作为子数组，因此也能得到正确结果。
动态规划的方法在处理大数组（如长度接近10^5）时仍然有效，因为它的时间复杂度是O(n)，这意味着算法对每个元素只进行一次操作。尽管如此，对于非常大的数组，还需要考虑内存使用和可能的整数溢出问题。在实际应用中，可能需要额外的逻辑来处理如整数溢出等边界和异常情况。