刷题笔记:力扣第53题-最大子数组和

1.根据题目提示，最快的解法一定是遍历一遍数组、时间复杂度为O(n)的算法。既然只遍历一遍数组，那么就要至少设置三个变量，一个是指向当前元素的指针cur，一个是储存本次计算得出的和数组和curSum，一个是储存目前得出的最大子数组和maxSum。

2.思考：什么情况下需要丢弃前面一段数组呢？可以想到的是，只要前面一段数组和为正数，那么一定是带上前面这段才可能得到最大子数组和；而当前面一段数组和为负数时，丢弃掉前面这段才可能得到得到最大子数组和。那么就需要额外定义一个储存之前数组和的变量preSum。

3.具体的思路为：curSum先初始化为0，用preSum记录上次curSum的值，如果preSum< 0则丢弃掉前面一段数组，让preSum重新初始化为0。每次都计算curSum等于preSum与当前数组元素的和，让maxSum等于过去的maxSum和curSum中的较大值。遍历完整个数组后即可得出最大子数组和。

完整代码如下：

1. // 自定义宏函数，用于比较两个数的大小，返回较大值 2. #define max(a, b) a > b ? a : b 3. 4. int maxSubArray(int* nums, int numsSize) { 5. // 定义变量 6. int cur, // cur：循环计数器，遍历数组的下标 7. preSum, // preSum：之前的累计和（判断是否为负数，决定是否清零） 8. curSum = 0, // curSum：当前连续子数组的累计和 9. maxSum = nums[0]; // maxSum：记录全局最大和（初始化为数组第一个元素，处理全负数情况） 10. 11. // 遍历整个数组 12. for (cur = 0; cur < numsSize; cur++){ 13. // 1. 把上一轮的累计和赋值给 preSum 14. preSum = curSum; 15. 16. // 2. 核心贪心思想： 17. // 如果前面的累计和是负数，那么它只会拖累当前数字，所以直接舍弃前面的，从0开始 18. if (preSum < 0){ 19. preSum = 0; 20. } 21. 22. // 3. 计算以当前数字结尾的最大子数组和 23. curSum = preSum + nums[cur]; 24. 25. // 4. 更新全局最大值：比较历史最大值和当前计算出的和，保留大的 26. maxSum = max(maxSum, curSum); 27. } 28. 29. // 遍历结束，返回最终的最大和 30. return maxSum; 31. }

该算法的本质为贪心算法，时间复杂度为O(n)，空间复杂度为O(1)，已经是最优解。

4.力扣官方希望解题者尝试一下分治法，简单来说就是“递归切割+合并”。分治法的思路为定义一个结构体存储左端点开始的最大子数组和、右端点开始的最大子数组和，这段区间的最大子数组和以及所有元素的子数组和，之后不断用get函数进行二分，递归分割到子数组只有一个元素后开始合并，算出新的结构体元素值，最后返回合并后的完整数组的最大子数组和即可。

5.代码+解析如下：

1. // 结构体：存储一段区间的4个关键状态 2. struct Status { 3. int lSum; // 从左端点开始的最大子数组和 4. int rSum; // 以右端点结束的最大子数组和 5. int mSum; // 这段区间的【最大子数组和】（最终答案） 6. int iSum; // 这段区间所有元素的总和 7. }; 8. 9. // 核心函数：合并左右两个子区间，计算出新的大区间状态 10. struct Status pushUp(struct Status l, struct Status r) { 11. // 1. 大区间的总和 = 左区间总和 + 右区间总和 12. int iSum = l.iSum + r.iSum; 13. 14. // 2. 新的 lSum：要么是左区间自己的 lSum，要么是左区间全量 + 右区间的 lSum 15. int lSum = fmax(l.lSum, l.iSum + r.lSum); 16. 17. // 3. 新的 rSum：要么是右区间自己的 rSum，要么是右区间全量 + 左区间的 rSum 18. int rSum = fmax(r.rSum, r.iSum + l.rSum); 19. 20. // 4. 新的 mSum（最重要）：三种情况取最大值 21. // 情况1：最大子数组在左区间 22. // 情况2：最大子数组在右区间 23. // 情况3：最大子数组跨越中间 24. int mSum = fmax(fmax(l.mSum, r.mSum), l.rSum + r.lSum); 25. 26. // 返回合并后的大区间状态 27. return (struct Status){lSum, rSum, mSum, iSum}; 28. }; 29. 30. // 递归函数：二分求解区间 [l, r] 的 Status 31. struct Status get(int* a, int l, int r) { 32. // 递归终止条件：区间只有一个数字 33. if (l == r) { 34. return (struct Status){a[l], a[l], a[l], a[l]}; 35. } 36. 37. // 二分：将区间从中间分成两半 38. int m = (l + r) >> 1; 39. 40. // 递归求解左半区间 41. struct Status lSub = get(a, l, m); 42. // 递归求解右半区间 43. struct Status rSub = get(a, m + 1, r); 44. 45. // 合并结果并返回 46. return pushUp(lSub, rSub); 47. } 48. 49. // 主函数入口 50. int maxSubArray(int* nums, int numsSize) { 51. // 求解整个数组 [0, numsSize-1] 的 Status，返回 mSum（答案） 52. return get(nums, 0, numsSize - 1).mSum; 53. }

其中fmax函数是C语言数学库自带的函数，作用就是输入两个数，返回较大数，和#define max(a, b) a > b ? a : b作用一样。

6.分治法的时间复杂度为O(nlogn)，虽然比贪心算法速度慢，但分治法的递归思想是很重要的，也需要掌握。