你的浏览器还没开启 Javascript 功能!

算法题(三)求子数组的最大和

前言

依稀记得此题在18年某次面试中遇到过,不过当时经验不足,虽然题目做出来了,但是不符合要求的时间复杂度O(n),现如今再次遇到,试试有没有新的思路吧。

题干

求子数组的最大和:
输入一个整形数组,数组里又正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。

要求:时间复杂度为O(n)。

举例:输入数组为1, -2, 3, 10, -4, 7, 2, -5,和为最大子数组为3, 10, -4, 7, 2,因此输出为该子数组的和18。

分析

  • 连续子数组最大和
  • 时间复杂度 O(n)

现在第一思路就是 动态规划,其它什么暴力循环,分治处理都实现不了O(n)的复杂度。

我们先理清题目中动态规划的几个要素:

状态转移公式

dp[i] = max{dp[i - 1] + a[i], a[i]}

这个公式结合题目通俗来讲就是:

假设 i = 5

前5个整数中,最大连续数组之和 = Max{(前4个最大数组之和 + 第5个整数) , 第五个整数}

边界

那很明显了,边界就是 a[i] 的值 和 前dp[i - 1]做比较,如果你a[i]比我之前累积的值还少,那我前面都白累加了,所以要放弃a[i],并把之前累积值置0

实现

公式概念讲起来有点绕,其实如果理解了概念的话,动态规划还是很常见的,尤其是算法题尤为常见。推荐大家不太清楚的可以去了解。

直接上代码吧,看如何实现


var arr = [1, -2, 3, 10, -4, 7, 2, -5];
var getMaxSum = function (arr) {
    var maxSum = 0;
    var tempSum = 0;
    for (var i = 0; i < arr.length; i++) {
        tempSum += arr[i];
        if (tempSum > maxSum) {
            maxSum = tempSum;
        }
        else if (tempSum < 0) {
            tempSum = 0;
        }
    }
    return maxSum;
};
console.log(getMaxSum(arr));

打印出的结果是18,而且时间复杂度满足了要求O(n),那可能代码中没看到公式呢?其实逻辑已经贯彻了,换个看起来有公式的也行。


var arr = [1, -2, 3, 10, -4, 7, 2, -5];
var getMaxSum = function (arr) {
    // 最大值
    var maxSum = 0;
    // 公式中的dp[i] 用来保存 累加的 值,因为只需要保存一个值,所以不需要dp数组
    var dp_sum = 0;
    for (var i = 0; i < arr.length; i++) {
        // dp[i] = max{dp[i - 1] + a[i], a[i]}
        dp_sum = Math.max(dp_sum + arr[i], arr[i]);

        // 判断更新最大值
        if(dp_sum > maxSum) {
            maxSum = dp_sum;
        }
    }
    return maxSum;
};
console.log(getMaxSum(arr));

蒽,这样,不知道你能否理解。