【LeetCode 53】最大子数组和（Maximum Subarray）题解
一、题目描述
给你一个整数数组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 <= 10^5-10^4 <= nums[i] <= 10^4
进阶：
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
二、解题分析
题目要求找出一个数组中和最大的连续子数组，这是一个经典的动态规划问题，也称为Kadane 算法。
核心思想：
用
currSum记录以当前元素结尾的最大子数组和。遍历数组，对于每一个元素：
如果
currSum为负数，则从当前元素重新开始；否则，将当前元素加入
currSum。
用
maxSum记录遍历过程中遇到的最大值。
动态规划转移方程：
currSum = max(nums[i], currSum + nums[i]) maxSum = max(maxSum, currSum)这里，currSum表示“以 nums[i] 结尾的最大连续子数组和”。
三、代码实现（C语言）
#include <stdio.h> int maxSubArray(int* nums, int numsSize) { if (numsSize == 0) return 0; int maxSum = nums[0]; // 全局最大子数组和 int currSum = nums[0]; // 以当前元素结尾的子数组和 for (int i = 1; i < numsSize; i++) { // 如果累加和为负数，从当前元素重新开始 if (currSum < 0) { currSum = nums[i]; } else { currSum += nums[i]; } // 更新全局最大值 if (currSum > maxSum) { maxSum = currSum; } } return maxSum; } // 测试 int main() { int nums[] = {-2,1,-3,4,-1,2,1,-5,4}; int size = sizeof(nums)/sizeof(nums[0]); printf("最大子数组和: %d\n", maxSubArray(nums, size)); return 0; }运行结果：
最大子数组和: 6四、复杂度分析
时间复杂度：O(n)
遍历数组一次即可。空间复杂度：O(1)
只需常数空间保存currSum和maxSum。
五、进阶解法：分治法（Divide and Conquer）
除了动态规划，还可以使用分治法解决：
将数组分为左右两半。
最大子数组和可能出现在：
左半部分
右半部分
跨越中间
递归求解左右两部分的最大值，再求跨越中间的最大值。
时间复杂度：O(n log n)
空间复杂度：O(log n) 递归栈空间
分治法思想非常经典，但实际面试中，Kadane 算法即可满足要求，且更高效。
六、总结
本题是典型的动态规划/Kadane算法问题。
核心在于“当前累加和为负数时，从当前元素重新开始”。
面试中，掌握动态规划思路即可，分治法为进阶拓展。
复杂度分析简单，O(n) 时间、O(1) 空间，非常优雅。