题目描述：

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例：

输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

解题思路：

这个问题可以使用动态规划来解决，经典的算法是Kadane算法。其核心思想是：

1. 初始化两个变量，max_current 和 max_global。max_current 表示以当前元素结尾的最大子数组和，max_global 表示全局的最大子数组和。
2. 遍历数组，对于每一个元素：
   • 更新 max_current 为当前元素和 max_current + 当前元素 中的较大值。
   • 更新 max_global 为 max_global 和 max_current 中的较大值。
3. 最终，max_global 就是最大子数组的和。

代码实现（Python）：

def maxSubArray(nums): if not nums: return 0

max_current = max_global = nums[0]

for i in range(1, len(nums)):
    max_current = max(nums[i], max_current + nums[i])
    max_global = max(max_global, max_current)

return max_global

nums = [-2,1,-3,4,-1,2,1,-5,4] print(maxSubArray(nums)) # 输出: 6

详细解释：

1. 初始化：
   • max_current 和 max_global 都初始化为数组的第一个元素 nums[0]。这是因为子数组至少包含一个元素，所以初始的最大子数组和就是第一个元素本身。
2. 遍历数组：
   • 从数组的第二个元素开始遍历（即索引为1的元素）。
   • 对于每一个元素 nums[i]，计算以 nums[i] 结尾的最大子数组和 max_current。这个值是当前元素 nums[i] 和 max_current + nums[i] 中的较大值。为什么要这样计算？因为如果 max_current 是负数，加上当前元素可能会使和变小，所以不如从当前元素重新开始计算子数组和。
   • 更新全局最大子数组和 max_global，这个值是 max_global 和 max_current 中的较大值。
3. 返回结果：
   • 遍历完数组后，max_global 就是最大子数组的和。

复杂度分析：

• 时间复杂度： O(n)，其中 n 是数组的长度。只需要遍历一次数组。
• 空间复杂度： O(1)，只需要常数级别的额外空间。

扩展：

• 如果数组中所有元素都是负数，Kadane算法仍然适用，最终返回的是最大的负数。
• 该算法可以扩展到二维数组，寻找最大子矩阵和的问题。

希望这个详细的解释和代码实现能帮助你理解并解决LeetCode 53题 “Maximum Subarray”。如果有任何进一步的问题，欢迎继续提问！