3196. 最大化子数组的总成本

发表于 分类于 阅读次数： Waline： 本文字数： 574 阅读时长 ≈ 2 分钟

考点

  • 划分DP

思路

把数组拆分为若干个连续的子数组，那么以每个点为结尾，向前枚举其区间，然后取最大值，这就是标准的划分DP做法

但是发现一个数学规律：

考虑一段： \[ [a_l, a_{l+1}, a_{l+2}, \dots, a_r] \] 它的 cost 是： \[ a_l - a_{l+1} + a_{l+2} - a_{l+3} + \dots \] 情况一：长度为偶数（例如 4 个数）

比如 [x0, x1, x2, x3]： \[ \text{cost} = x_0 - x_1 + x_2 - x_3 \] 把它分成两段 [x0, x1] 和 [x2, x3]，分别算 cost：

  • [x0, x1]：x0 - x1
  • [x2, x3]：x2 - x3

两段加起来：(x0 - x1) + (x2 - x3) —— 刚好等于原来整段的 cost。

推广一下：对于任意偶数长度 \(2m\)： \[ x_0 - x_1 + x_2 - x_3 + \dots + x_{2m-2} - x_{2m-1} \] 可以拆成： \[ (x_0 - x_1) + (x_2 - x_3) + \dots + (x_{2m-2} - x_{2m-1}) \] 也就是说：偶数长度的一段，可以拆成若干个长度为 2 的小段，总代价完全一样。

情况二：长度为奇数（例如 5 个数）

比如 [x0, x1, x2, x3, x4]： \[ \text{cost} = x_0 - x_1 + x_2 - x_3 + x_4 \] 把它拆成三段 [x0,x1], [x2,x3], [x4]：

  • [x0,x1]：x0 - x1
  • [x2,x3]：x2 - x3
  • [x4]：x4

加起来：(x0 - x1) + (x2 - x3) + x4 —— 也是刚好等于原来的 cost。

同理，长度为 \(2m+1\) 的一段： \[ x_0 - x_1 + x_2 - x_3 + \dots + x_{2m} \] 可以拆成： \[ (x_0 - x_1) + (x_2 - x_3) + \dots + (x_{2m-2} - x_{2m-1}) + x_{2m} \] 也就是说：奇数长度的一段，可以拆成若干个长度为 2 的段，外加最后一个长度为 1 的段，总代价完全一样。

也就是说，我们只需要管最后两个数字就好了，即

1
f[i]=max(f[i−1]+a[i−1], f[i−2]+a[i−2]−a[i−1])

可以得到如下DP：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    static const int maxn = 1e5 + 5;
    long long maximumTotalCost(vector<int>& nums) {
        long long f[maxn];
        memset(f, 0xcf, sizeof(f));
        f[0] = 0;
        int n = nums.size();
        for (int i = 1; i <= n; ++i) {
            f[i] = max(f[i], f[i - 1] + nums[i - 1]);
            if (i >= 2)
                f[i] = max(f[i], f[i - 2] - nums[i - 1] + nums[i - 2]);
        }
        return f[n];
    }
};

当然，由于只用到了前面两个数字，用不到数组，所以直接用变量替代：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
 public:
  static const int maxn = 1e5 + 5, neg = 0xcfcfcfcf;
  long long maximumTotalCost(vector<int>& nums) {
    long long one = nums[0], two = 0;
    for (int i = 2; i <= nums.size(); ++i) {
      long long t = neg;
      t = max(t, max(one + nums[i - 1], two - nums[i - 1] + nums[i - 2]));
      two = one;
      one = t;
    }
    return one;
  }
};