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

You are given a 0-indexed array of integers nums of length n, and a positive odd integer k.

The strength of x subarrays is defined as strength = sum[1] * x - sum[2] * (x - 1) + sum[3] * (x - 2) - sum[4] * (x - 3) + ... + sum[x] * 1 where sum[i] is the sum of the elements in the ith subarray. Formally, strength is sum of (-1)i+1 * sum[i] * (x - i + 1) over all i's such that 1 <= i <= x.

You need to select k disjoint subarrays from nums, such that their strength is maximum.

Return the maximum possible strength that can be obtained.

Note that the selected subarrays don't need to cover the entire array.

 

Example 1:

Input: nums = [1,2,3,-1,2], k = 3
Output: 22
Explanation: The best possible way to select 3 subarrays is: nums[0..2], nums[3..3], and nums[4..4]. The strength is (1 + 2 + 3) * 3 - (-1) * 2 + 2 * 1 = 22.

Example 2:

Input: nums = [12,-2,-2,-2,-2], k = 5
Output: 64
Explanation: The only possible way to select 5 disjoint subarrays is: nums[0..0], nums[1..1], nums[2..2], nums[3..3], and nums[4..4]. The strength is 12 * 5 - (-2) * 4 + (-2) * 3 - (-2) * 2 + (-2) * 1 = 64.

Example 3:

Input: nums = [-1,-2,-3], k = 1
Output: -1
Explanation: The best possible way to select 1 subarray is: nums[0..0]. The strength is -1.

 

Constraints:

• 1 <= n <= 104
• -109 <= nums[i] <= 109
• 1 <= k <= n
• 1 <= n * k <= 106
• k is odd.

/*
题目思路：
1. 计算每个可能的子数组的和并存储在一个二维数组中。
2. 使用Java Stream API来简化动态规划的部分。
3. 遍历所有可能的子数组组合，更新dp数组。
4. 最后，返回dp数组的最大值。
*/

import java.util.stream.IntStream;

public class Solution {
    public int maxEnergy(int[] nums, int k) {
        int n = nums.length;
        int[][] sum = new int[n][n];
        for (int i = 0; i < n; i++) {
            sum[i][i] = nums[i];
            for (int j = i + 1; j < n; j++) {
                sum[i][j] = sum[i][j - 1] + nums[j];
            }
        }

        int[][] dp = new int[n + 1][k + 1];
        IntStream.range(1, n + 1).forEach(i -> {
            IntStream.range(1, k + 1).forEach(j -> {
                IntStream.range(0, i).forEach(l -> {
                    int energy = IntStream.range(0, j).map(m -> (int) (Math.pow(-1, m + 1) * sum[l][i - 1] * (j - m))).sum();
                    dp[i][j] = Math.max(dp[i][j], dp[l][j - 1] + energy);
                });
            });
        });
        return dp[n][k];
    }
}

本题解采用动态规划的方式来求解。首先，计算数组 `nums` 的累加和 `acc`，这是为了快速计算任意子数组的和。然后，定义动态规划数组 `dps`，其中 `dps[i]` 表示在数组前 `i` 个元素中选取 `ck` 个子数组能够获得的最大能量值。对于每一个可能的 `k`，计算对应的权重 `cw`，这个权重根据 `k` 的值和当前子数组的索引 `ck` 而有所不同，具体为 `(-1)^ck * (k - ck)`。接着，遍历数组使用滚动数组方式更新 `dps`，每次考虑加入新的子数组时，更新 `dps[i]` 为包括新子数组的最大能量值。这个过程中，我们需要维护当前的最大值 `curs` 以便快速更新 `dps`。最终 `dps[-1]` 将包含在整个数组中选取 `k` 个子数组的最大能量值。

O(n^2)

O(n)