【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) 空间非常优雅。