推导 Kadane算法(JavaScript)

1,345 阅读2分钟

本文是我在学习 LeetCode-最大子序和 多解法时偶然发现的哈

由于我只是小小前端开发,日常工作跟算法相关的也不多,表达不当或理解不对的地方,感谢您点评指正~

本文解一到解四,是一个递进和推导的过程。

场景

最大子序和

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

示例:

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

解一:暴力法 O(n^3)

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let maxSum = -Infinity;
    for (let i = 0; i < nums.length; i++) {
        for (let j = i; j < nums.length; j++) {
            let sum = -Infinity;
            for (let t = i; i <= j; t++) {
                sum += t;
            }
            if (maxSum < sum) {
                maxSum = sum;
            }
        }
    }
    return maxSum;
};

这种超出时间限制

解二: 优化暴力法 O(n^2)

去掉 t 的遍历,对 sum 计算的优化

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let maxSum = -Infinity;
    for (let i = 0; i < nums.length; i++) {
        let sum = 0;
        for (let j = i; j < nums.length; j++) {
            sum += nums[j];
            if (maxSum < sum) {
                maxSum = sum;
            }
        }
    }
    return maxSum;
};

解三:动态规划 T(n) = O(n) S(n) = O(n)

  1. 动态规划其实是对解二的优化, 去掉 j 的迭代
  2. 上面的每个 i 的迭代,是以 i 为起点(含 i),j 为终点求 sum
  3. 假设 DP[i] 表示以 i 为起点(含 i)到终点的连续子序列的最大和
  4. DP 递推公式 DP[i] = Math.max(nums[i], nums[i] + DP[i+1])
  5. 由于 DP[i+1] 是先得到的,需要从后往前计算。反过来
  6. 假设 DP[i] 表示从第一个元素开始到 i (含 i)中连续子序列的最大和
  7. DP 递推公式 DP[i] = Math.max(nums[i], nums[i] + DP[i-1])

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let maxSum = -Infinity;
    const DP = Array(nums.length);    
    for (let i = 0; i < nums.length; i++) {
        if (i === 0) {
            DP[0] = maxSum = nums[0];
            continue;
        }
        DP[i] = Math.max(nums[i], nums[i] + DP[i-1])
        if (maxSum < DP[i]) {
            maxSum = DP[i];
        }
    }
    return maxSum;
};

解四:Kadane算法 T(n) = O(n) S(n) = O(1)

在解三动态规划中,for 循环只用到 DP[i] DP[i-1], 并不需要用整个 Array(nums.length),用一个变量 DP_i 即可

var maxSubArray = function(nums) {
    let maxSum = -Infinity;
    let DP_i;
    for (let i = 0; i < nums.length; i++) {
        if (i === 0) {
            DP_i = maxSum = nums[0];
            continue;
        }
        DP_i = Math.max(nums[i], nums[i] + DP_i);
        if (maxSum < DP_i) {
            maxSum = DP_i;
        }
    }
    return maxSum;
};

DP_i 表示以从第一个元素开始到 i (含 i)中连续子序列的最大和,如代码所示,优化后的公式为

DP_i = Math.max(nums[i], nums[i] + DP_i);

其实这就是著名的 Kadane算法, 参见 维基百科 - 最大子数列问题