https://leetcode.cn/problems/maximum-subarray/?envType=study-plan-v2&envId=top-100-liked

image-20260327173820680

核心逻辑： Kadane 算法（动态规划）

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int maxSubArray(int[] nums) {
        int maxsum=nums[0];
        int maxcurrent=nums[0];
        for(int i=1;i<nums.length;i++){
            maxcurrent=Math.max(nums[i],maxcurrent+nums[i]);
            maxsum=Math.max(maxcurrent,maxsum);
        }
        return maxsum;
    }
}

1. 核心决策：你要不要“另起炉灶”？

在遍历数组的每一个数字 nums[i] 时，算法都在做一个至关重要的决定： 是以 nums[i] 为结尾，继续接在前面的子数组后面？还是干脆放弃前面，从 nums[i] 开始重新计算？

这行代码就是这个决策的体现： maxcurrent = Math.max(nums[i], maxcurrent + nums[i]);

  • 如果 maxcurrent + nums[i] 比较大：说明前面的累加（maxcurrent）对我有正面贡献（它是正数），那我就带着它。
  • 如果 nums[i] 本身比较大：说明前面的累加是个“累赘”（它是负数），加上它反而让我变小了。那我就果断“断舍离”，从现在的 nums[i] 重新开始。

2. 两个变量的作用

  • maxcurrent (局部最优)： 它代表的是以当前元素 i 结尾的所有子数组中，和最大的那一个。它像是一个“短跑运动员”，只管跑好当前的这一段。
  • maxsum (全局最优)： 它负责记录在这个过程中出现过的最高分。它是“纪录保持者”，只要 maxcurrent 创造了新高，它就更新。

贪心版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxSubArray(int[] nums) {
        int sum = nums[0]; // 直接用第一个元素初始化
        int count = 0;
        for (int x : nums) {
            count += x;
            sum = Math.max(sum, count); // 先更新最大值
            if (count < 0) {
                count = 0; // 只要亏本了，就重置
            }
        }
        return sum;
    }
}