1._最大子数组和

• 动态规划

• 2.25

  • 放下包裹并不是与 0 对比，而是与 nums【i】对比
  • 谈心记录最大值

• 2.7

  • 类似与动态规划与贪心算法
    • 每次动态规划时，选择是加入前面的包袱加自己还是从自己开始，dp 数组的含义是每个位置存储的最大重量

• 1.23

  • 忘记状态转移公式了，记录全局最大值为数组的第一个

• 1.12

  • 一开始觉得眼熟，知道是动态思路后能做，但有个 bug
  • 就是 maxValue 初值应该是数组第一个数字，而不是极小值或者 0

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        //int maxValue = Integer.MIN_VALUE;
        int maxValue = nums[0];
        for(int i=1;i<nums.length;i++){
            dp[i] = Math.max(nums[i],dp[i-1]+nums[i]);
            maxValue = Math.max(dp[i],maxValue);
        }
        return maxValue;
    }
}

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = nums[0];
        int dp = nums[0];
        for(int i = 1; i<nums.length;i++){
            dp = Math.max(nums[i],dp+nums[i]);//这里的dp是dp[i-1]]
            maxSum = Math.max(maxSum,dp);
        }
        return maxSum;
    }
}

• 状态转移方程

$dp[i]=max(dp[i−1]+nums[i], nums[i])$

🧠 直觉理解（形象比喻） 你可以把它想成“背负行李走路”：

• 你每走一步，就加上一个值（当前元素的分数）；
• 如果背包里的总和是负数，那就把包清空（重新开始）；
• 你只记录走到现在为止的最重的“包”（最大和）。