算法动态规划

增删改后的最大子数组和

字数统计: 2k字   |   阅读时长: 8分
,

摘要: 本文介绍最大子数组和的一类变种：可以增删改的情况

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 最大子数组和的三种解法 中，我们详细拆解了最大子数组和这个问题，并且了解到这个问题有三种解法，都非常主流，并且各个方法都有它适用的变种问题。

此前我们已经见过了三种类型的变种，第一类是【数组->矩阵】、【数组->环形数组】这种比较直接的变种。这类问题比较关键的是对问题进行转化，把环形数组或矩阵上的问题转化为数组上的问题。只要正确转化为了数组上的问题，那么数组上的三种方法都是可以用的。参考文章 环形数组上的最大子数组和 和 最大子矩阵和。

第二类是对求和的过程增加限制，例如 带大小限制的最大子数组/子矩阵和 中的限制子数组和不大于 k，带长度限制的最大子数组和 中的限制子数组长度不大于 m。这类变种主要通过前缀和+单调队列解决比较方便。

第三类也比较直接，就是把求和这个操作改成乘积。这类问题的关键是处理好负数和零的问题，用动态规划来解决最方便，参考文章 最大子数组乘积。

本文我们看第四类变种，也就是给定原数组，问对数组进行若干增删改的操作后的最大子数组和。这类变种就更加灵活了，因为增删改的方式有无数种，因此只能具体问题具体分析，本文我们看两个题，这两个问题的处理方式都是先用动态规划求出原数组以 i 结尾的最大子数组和 dp1[i]、以 i 开头的最大子数组和 dp2[i]，然后基于 dp1 和 dp2 中的信息进行一些后处理得到答案。

题目1

给定一个整数数组 arr 和一个整数 k ，通过重复 k 次来修改数组。

例如，如果 arr = [1, 2] ， k = 3 ，那么修改后的数组将是 [1, 2, 1, 2, 1, 2] 。

返回修改后的数组中的最大的子数组之和。注意，子数组长度可以是 0，在这种情况下它的总和也是 0。

由于 结果可能会很大，需要返回的 1e9 + 7 的 模 。

提示：

1
2
3
1 <= arr.length <= 1e5
1 <= k <= 1e5
-1e4 <= arr[i] <= 1e4

示例 1：
输入：arr = [1,2], k = 3
输出：9
示例 2：
输入：arr = [1,-2,1], k = 5
输出：2
示例 3：
输入：arr = [-1,-2], k = 7
输出：0

算法: 动态规划

本题中原数组可以复制多份拼在末尾，因此除了原数组上的最大子数组和可能是答案以外，答案还有可能横跨两个数组甚至更多个数组。

我们用动态规划求出原数组上以 i 结尾的最大子数组和 dp1[i] 以及以 i 开头的最大子数组和 dp2[i]。

首先 max(dp1[i]) 是原数组上的最大子数组和，这有可能是答案。

dp1[n-1] 对应原数组的某段后缀，dp2[0] 对应原数组的某段前缀，因此如果 dp1[n-1] > 0 且 dp2[0] > 0，那么对应的前缀和后缀拼在一起形成的子数组的和大于零，那么 dp1[n -1] + dp2[0] 它也有可能是答案。

再进一步，如果原数组整体的和 sum 就大于零，dp1[n-1] 和 dp2[0] 之间插入越多的原数组，最终的子数组和就越大，因此 dp1[n-1] + dp2[0] + (k - 2) * sum 也有可能是答案。

最终算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
状态定义：
dp1[i] := [0..i] 上以 i 为结尾的最大字数组和
dp2[i] := [i..n-1] 上以 i 为开头的最大字数组和

答案：
max(dp1[i]
   ,dp1[n - 1] + dp2[0]
   ,dp1[n - 1] + dp2[0] + (k + 2) * sum
   )

初始化：
dp1[0] = nums[0]
dp2[n - 1] = nums[n - 1];

状态转移：
dp1[i] = nums[i] + max(dp1[i - 1], 0)
dp2[i] = nums[i] + max(dp2[i + 1], 0)

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int kConcatenationMaxSum(vector<int>& arr, int k) {
        int n = arr.size();
        vector<int> dp1(n, 0);
        vector<int> dp2(n, 0);
        dp1[0] = arr[0];
        dp2[n - 1] = arr[n - 1];
        ll sum = arr[0];
        ll ans = max(0, arr[0]);
        for(int i = 1; i < n; ++i)
        {
            sum += arr[i];
            dp1[i] = arr[i] + max(dp1[i - 1], 0);
            ans = max(ans, (ll)dp1[i]);
        }
        for(int i = n - 2; i >= 0; --i)
            dp2[i] = arr[i] + max(dp2[i + 1], 0);
        if(k > 1)
        {
            ans = max(ans, (ll)dp1[n - 1] + dp2[0]);
            ans = max(ans, (dp1[n - 1] + (ll)dp2[0] + (k - 2) * sum));
        }
        return ans % MOD;
    }

private:
    const int MOD = 1e9 + 7;
    using ll = long long;
};

题目2

给你一个整数数组，返回它的某个 非空 子数组（连续元素）在执行一次可选的删除操作后，所能得到的最大元素总和。换句话说，你可以从原数组中选出一个子数组，并可以决定要不要从中删除一个元素（只能删一次哦），（删除后）子数组中至少应当有一个元素，然后该子数组（剩下）的元素总和是所有子数组之中最大的。

注意，删除一个元素后，子数组 不能为空。

提示：

1
2
1 <= arr.length <= 1e5
-1e4 <= arr[i] <= 1e4

示例 1：
输入：arr = [1,-2,0,3]
输出：4
解释：我们可以选出 [1, -2, 0, 3]，然后删掉 -2，这样得到 [1, 0, 3]，和最大。
示例 2：
输入：arr = [1,-2,-2,3]
输出：3
解释：我们直接选出 [3]，这就是最大和。
示例 3：
输入：arr = [-1,-1,-1,-1]
输出：-1
解释：最后得到的子数组不能为空，所以我们不能选择 [-1] 并从中删去 -1 来得到 0。
我们应该直接选择 [-1]，或者选择 [-1, -1] 再从中删去一个 -1。

算法: 动态规划

本题中原数组中可以删除一个数，因此除了原数组上的最大子数组和可能是答案以外，被删元素的位置的左边一段和右边一段组成的子数组也有可能是答案。

假设被删的位置是 p，那么如果我们知道以 p-1 为结尾的最大子数组和 dp1[p-1] 和以 p+1 为开头的最大子数组和 dp2[p+1]，那么 dp1[p-1] + dp2[p+1] 也就有可能是答案。

dp1[i] 和 dp2[i] 的求法与前一题一模一样，用动态规划即可，完整算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
状态定义：
dp1[i] := [0..i] 上以 i 为结尾的最大字数组和
dp2[i] := [i..n-1] 上以 i 为开头的最大字数组和

答案：
max(dp1[i] 
    dp1[p - 1] + dp2[p + 1]
   )

初始化：
dp1[0] = nums[0]
dp2[n - 1] = nums[n - 1];

状态转移：
dp1[i] = nums[i] + max(dp1[i - 1], 0)
dp2[i] = nums[i] + max(dp2[i + 1], 0)

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maximumSum(vector<int>& arr) {
        int n = arr.size();
        vector<int> dp1(n), dp2(n);
        dp1[0] = arr[0];
        int ans = arr[0];
        for(int i = 1; i < n; ++i)
        {
            dp1[i] = max(dp1[i - 1] + arr[i], arr[i]);
            ans = max(ans, dp1[i]);
        }
        dp2[n - 1] = arr[n - 1];
        for(int i = n - 2; i >= 0; --i)
            dp2[i] = max(dp2[i + 1] + arr[i], arr[i]);
        for(int p = 1; p < n - 1; ++p)
            ans = max(ans, dp1[p - 1] + dp2[p + 1]);
        return ans;
    }
};
Share