class Solution {
public:
long long maximumStrength(vector<int>& nums, int k) {
}
};
3077. 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 <= 104-109 <= nums[i] <= 1091 <= k <= n1 <= n * k <= 106k 是奇数。原站题解
golang 解法, 执行用时: 33 ms, 内存消耗: 18.5 MB, 提交时间: 2024-03-13 20:29:24
func maximumStrength(nums []int, k int) int64 {
n := len(nums)
s := make([]int, n+1)
for i, x := range nums {
s[i+1] = s[i] + x
}
f := make([][]int, k+1)
f[0] = make([]int, n+1)
for i := 1; i <= k; i++ {
f[i] = make([]int, n+1)
f[i][i-1] = math.MinInt
mx := math.MinInt
w := (k - i + 1) * (i%2*2 - 1)
// j 不能太小也不能太大，要给前面留 i-1 个数，后面留 k-i 个数
for j := i; j <= n-k+i; j++ {
mx = max(mx, f[i-1][j-1]-s[j-1]*w)
f[i][j] = max(f[i][j-1], s[j]*w+mx)
}
}
return int64(f[k][n])
}
cpp 解法, 执行用时: 94 ms, 内存消耗: 127.2 MB, 提交时间: 2024-03-13 20:29:10
class Solution {
public:
long long maximumStrength(vector<int> &nums, int k) {
int n = nums.size();
vector<long long> s(n + 1);
for (int i = 0; i < n; i++) {
s[i + 1] = s[i] + nums[i];
}
vector<vector<long long>> f(k + 1, vector<long long>(n + 1));
for (int i = 1; i <= k; i++) {
f[i][i - 1] = LLONG_MIN;
long long mx = LLONG_MIN;
int w = (k - i + 1) * (i % 2 ? 1 : -1);
// j 不能太小也不能太大，要给前面留 i-1 个数，后面留 k-i 个数
for (int j = i; j <= n - k + i; j++) {
mx = max(mx, f[i - 1][j - 1] - s[j - 1] * w);
f[i][j] = max(f[i][j - 1], s[j] * w + mx);
}
}
return f[k][n];
}
};
java 解法, 执行用时: 22 ms, 内存消耗: 58.9 MB, 提交时间: 2024-03-13 20:28:56
class Solution {
public long maximumStrength(int[] nums, int k) {
int n = nums.length;
long[] s = new long[n + 1];
for (int i = 0; i < n; i++) {
s[i + 1] = s[i] + nums[i];
}
long[][] f = new long[k + 1][n + 1];
for (int i = 1; i <= k; i++) {
f[i][i - 1] = Long.MIN_VALUE;
long mx = Long.MIN_VALUE;
int w = (k - i + 1) * (i % 2 > 0 ? 1 : -1);
// j 不能太小也不能太大，要给前面留 i-1 个数，后面留 k-i 个数
for (int j = i; j <= n - k + i; j++) {
mx = Math.max(mx, f[i - 1][j - 1] - s[j - 1] * w);
f[i][j] = Math.max(f[i][j - 1], s[j] * w + mx);
}
}
return f[k][n];
}
}
python3 解法, 执行用时: 1696 ms, 内存消耗: 62.6 MB, 提交时间: 2024-03-13 20:28:42
class Solution:
def maximumStrength(self, nums: List[int], k: int) -> int:
n = len(nums)
s = list(accumulate(nums, initial=0))
f = [[0] * (n + 1) for _ in range(k + 1)]
for i in range(1, k + 1):
f[i][i - 1] = mx = -inf
w = (k - i + 1) * (1 if i % 2 else -1)
# j 不能太小也不能太大，要给前面留 i-1 个数，后面留 k-i 个数
for j in range(i, n - k + i + 1):
mx = max(mx, f[i - 1][j - 1] - s[j - 1] * w)
f[i][j] = max(f[i][j - 1], s[j] * w + mx)
return f[k][n]