K 个不相交子数组的最大能量值

题目

100216. K 个不相交子数组的最大能量值

---

给你一个长度为 n 下标从 0 开始的整数数组 nums 和一个 正奇数 整数 k 。

x 个子数组的能量值定义为 strength = sum[1] * x - sum[2] * (x - 1) + sum[3] * (x - 2) - sum[4] * (x - 3) + ... + sum[x] * 1 ，其中 sum[i] 是第 i 个子数组的和。更正式的，能量值是满足 1 <= i <= x 的所有 i 对应的 (-1)^i+1 * sum[i] * (x - i + 1) 之和。

你需要在 nums 中选择 k 个 不相交****子数组 ，使得 能量值最大 。

请你返回可以得到的 最大****能量值 。

注意，选出来的所有子数组 不 需要覆盖整个数组。

示例 1：

输入：nums = [1,2,3,-1,2], k = 3
输出：22
解释：选择 3 个子数组的最好方式是选择：nums[0..2] ，nums[3..3] 和 nums[4..4] 。能量值为 (1 + 2 + 3) * 3 - (-1) * 2 + 2 * 1 = 22 。

示例 2：

输入：nums = [12,-2,-2,-2,-2], k = 5
输出：64
解释：唯一一种选 5 个不相交子数组的方案是：nums[0..0] ，nums[1..1] ，nums[2..2] ，nums[3..3] 和 nums[4..4] 。能量值为 12 * 5 - (-2) * 4 + (-2) * 3 - (-2) * 2 + (-2) * 1 = 64 。

示例 3：

输入：nums = [-1,-2,-3], k = 1
输出：-1
解释：选择 1 个子数组的最优方案是：nums[0..0] 。能量值为 -1 。

提示：

• 1 <= n <= 10^4
• -10^9 <= nums[i] <= 10^9
• 1 <= k <= n
• 1 <= n * k <= 10^6
• k 是奇数。

题解

方法一：

思路

定义$f_{i,j,c}$第i个数是是/否（c=1/0）属于第j组的情况下，得到的最大值。答案是划分k组的最大值$f_{?,k,?}$。

第i个数不属于j组，$f_{i,j,0} = max(f_{i-1,j-1,0}, f_{i-1,j-1,1})$

第i个数属于j组，属于新划分一组$f_{i,j,1} = max(f_{i-1,j-1,0}, f_{i-1,j-1,1})+(-1)^{(j+1)}(k-j+1)a_{i-1}$，不属于新划分的一组$f_{i,j,1} = f_{i-1,j,1}+(-1)^{(j+1)}(k-j+1)a_{i-1}$

代码

class Solution {
public:
    using ll = long long;
    long long maximumStrength(vector<int>& nums, int k) {
        int n = nums.size();
        ll f[n+1][k+1][2];
        for (int i=0; i<=n; i++) {
            for (int j=0; j<=k; j++) {
                f[i][j][0] = f[i][j][1] = -1e17;
            }
        }
        f[0][0][0] = 0;
        for (int i=1; i<=n; i++) {
            for (ll j=0; j<=k; j++) {
                f[i][j][0] = max(f[i-1][j][0], f[i-1][j][1]);
                f[i][j][1] = f[i-1][j][1]+(j%2?(k-j+1):-(k-j+1))*nums[i-1];
                if (j>0) {
                    f[i][j][1] = max(f[i][j][1], max(f[i-1][j-1][0], f[i-1][j-1][1])+(j%2?(k-j+1):-(k-j+1))*nums[i-1]);
                }
            }
        }
        ll ans = -1e17;
        for (int i=1; i<=n; i++) {
            ans = max({ans, f[i][k][0], f[i][k][1]});
        }
        return ans;
    }
};