最大子序和

LeetCode

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

每个算法，用生活中的例子加以解释，就会记忆深刻，理解透彻了

示例

1
2
3
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

答案

1
2
3
4
5
6
7
8
var maxSubArray = function(nums) {
    let totalPlus = 0, maxPlus = nums[0];
    nums.forEach((x) => {
        totalPlus = Math.max(totalPlus + x, x);
        maxPlus = Math.max(maxPlus, totalPlus);
    });
    return maxPlus;
};

举例说明

  1. 假设现在有一个空的桶，上方加水，底部快慢不一的放水
  2. 加水，可以理解为，将数组的每个数字加入桶里面
  3. 放水，可以理解为，当数字为负数时，开始放出相应的水量
  4. 最后操作结束，可以看到桶内壁处的最高水印位置，即当前出现的最大和

https://leetcode-cn.com/problems/maximum-subarray/comments/1114786

动态规划

动规五部曲

  1. 确定dp数组，以及下标的含义
    dp[i]：包括下标i之前的最⼤连续⼦序列和为dp[i]。
  2. 确定递归公式
    dp[i]只有两个⽅向可以推出来：
  • dp[i - 1] + nums[i]，即：nums[i]加⼊当前连续⼦序列和
  • nums[i]，即：从头开始计算当前连续⼦序列和
    ⼀定是取最⼤的，所以dp[i] = max(dp[i - 1] + nums[i], nums[i]);
  1. dp数组如何初始化
    从递推公式可以看出来dp[i]是依赖于dp[i - 1]的状态，dp[0]就是递推公式的基础。
    即dp[0] = nums[0]
  2. 确定遍历顺序递推公式中dp[i]依赖于dp[i - 1]的状态，需要从前向后遍历。
  3. 举例推导dp数组
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    // 输⼊：nums = [-2,1,-3,4,-1,2,1,-5,4]，对应的dp状态如下：
    // dp[i] = max(dp[i - 1] + nums[i], nums[i]);
    dp[0] = -2   max(-2)  
    dp[1] = 1    max(-1,1)
    dp[2] = -2   max(-2,-3)
    dp[3] = 4    max(2,4)
    dp[4] = 3    max(3,-1)
    dp[5] = 5    max(5,2)
    dp[6] = 6    max(6,1)
    dp[7] = 1    max(1,-5)
    dp[8] = 5    max(5,4)
    那么我们要找最⼤的连续⼦序列，就应该找每⼀个i为终点的连续最⼤⼦序列。所以在递推公式的时候，可以直接选出最⼤的dp[i]。
1
2
3
4
5
6
7
8
9
10
11
var maxSubArray = function(nums) {
    // dp[i] = max{dp[i-1]+v, v}
    const dp = [];
    dp[0] = arr[0];
    let max = dp[0];
    for (let i = 1; i < arr.length; i++) {
        dp[i] = Math.max(dp[i - 1] + arr[i], arr[i]);
        max = Math.max(max, dp[i]);
    }
    return max;
};
LeetCode