乐趣区

关于segmentfault:最大子序和

读完本文,你能够去力扣拿下如下题目:

53. 最大子序和

———–

最大子数组问题和前文讲过的 经典动静布局:最长递增子序列 的套路十分类似,代表着一类比拟非凡的动静布局问题的思路:

思路剖析

其实第一次看到这道题,我首先想到的是滑动窗口算法,因为咱们前文说过嘛,滑动窗口算法就是专门解决子串 / 子数组问题的,这里不就是子数组问题么?

然而,稍加剖析就发现,这道题还不能用滑动窗口算法,因为数组中的数字能够是正数

滑动窗口算法无非就是双指针造成的窗口扫描整个数组 / 子串,但要害是,你得分明地晓得什么时候应该挪动右侧指针来扩充窗口,什么时候挪动左侧指针来减小窗口。

而对于这道题目,你想想,当窗口扩充的时候可能遇到正数,窗口中的值也就可能减少也可能缩小,这种状况下不晓得什么机会去膨胀左侧窗口,也就无奈求出「最大子数组和」。

解决这个问题须要动静布局技巧,然而 dp 数组的定义比拟非凡。依照咱们惯例的动静布局思路,个别是这样定义 dp 数组:

nums[0..i] 中的「最大的子数组和」为 dp[i]

如果这样定义的话,整个 nums 数组的「最大子数组和」就是 dp[n-1]。如何找状态转移方程呢?依照数学归纳法,假如咱们晓得了 dp[i-1],如何推导出 dp[i] 呢?

如下图,依照咱们方才对 dp 数组的定义,dp[i] = 5,也就是等于 nums[0..i] 中的最大子数组和:

那么在上图这种状况中,利用数学归纳法,你能用 dp[i] 推出 dp[i+1] 吗?

实际上是不行的,因为子数组肯定是间断的,依照咱们以后 dp 数组定义,并不能保障 nums[0..i] 中的最大子数组与 nums[i+1] 是相邻的,也就没方法从 dp[i] 推导出 dp[i+1]

所以说咱们这样定义 dp 数组是不正确的,无奈失去适合的状态转移方程。对于这类子数组问题,咱们就要从新定义 dp 数组的含意:

nums[i] 为结尾的「最大子数组和」为 dp[i]

PS:我认真写了 100 多篇原创,手把手刷 200 道力扣题目,全副公布在 labuladong 的算法小抄,继续更新 。倡议珍藏, 依照我的文章程序刷题,把握各种算法套路后投再入题海就蛟龙得水了。

这种定义之下,想得到整个 nums 数组的「最大子数组和」,不能间接返回 dp[n-1],而须要遍历整个 dp 数组:

int res = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {res = Math.max(res, dp[i]);
}
return res;

仍然应用数学归纳法来找状态转移关系:假如咱们曾经算出了 dp[i-1],如何推导出 dp[i] 呢?

能够做到,dp[i] 有两种「抉择」,要么与后面的相邻子数组连贯,造成一个和更大的子数组;要么不与后面的子数组连贯,自成一派,本人作为一个子数组。

如何抉择?既然要求「最大子数组和」,当然抉择后果更大的那个啦:

// 要么自成一派,要么和后面的子数组合并
dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);

综上,咱们曾经写出了状态转移方程,就能够间接写出解法了:

int maxSubArray(int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;
    int[] dp = new int[n];
    // base case
    // 第一个元素后面没有子数组
    dp[0] = nums[0];
    // 状态转移方程
    for (int i = 1; i < n; i++) {dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
    }
    // 失去 nums 的最大子数组
    int res = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {res = Math.max(res, dp[i]);
    }
    return res;
}

以上解法工夫复杂度是 O(N),空间复杂度也是 O(N),较暴力解法曾经很优良了,不过 留神到 dp[i] 仅仅和 dp[i-1] 的状态无关,那么咱们能够进行「状态压缩」,将空间复杂度升高:

int maxSubArray(int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;
    // base case
    int dp_0 = nums[0];
    int dp_1 = 0, res = dp_0;

    for (int i = 1; i < n; i++) {// dp[i] = max(nums[i], nums[i] + dp[i-1])
        dp_1 = Math.max(nums[i], nums[i] + dp_0);
        dp_0 = dp_1;
        // 顺便计算最大的后果
        res = Math.max(res, dp_1);
    }
    
    return res;
}

最初总结

尽管说动静布局推状态转移方程的确比拟玄学,但大部分还是有些法则可循的。

明天这道「最大子数组和」就和「最长递增子序列」十分相似,dp 数组的定义是「以 nums[i] 为结尾的最大子数组和 / 最长递增子序列为 dp[i]」。因为只有这样定义能力将 dp[i+1]dp[i] 建设起分割,利用数学归纳法写出状态转移方程。

_____________

我的 在线电子书 有 100 篇原创文章,手把手带刷 200 道力扣题目,倡议珍藏!对应的 GitHub 算法仓库 曾经取得了 70k star,欢送标星!

退出移动版