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)虽然比贪心算法速度慢但分治法的递归思想是很重要的也需要掌握。
刷题笔记:力扣第53题-最大子数组和
发布时间：2026/7/30 21:48:03
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)虽然比贪心算法速度慢但分治法的递归思想是很重要的也需要掌握。
)
