class Solution {
public:
long long maximumTotalCost(vector<int>& nums) {
}
};
100337. 最大化子数组的总成本
给你一个长度为 n 的整数数组 nums。
子数组 nums[l..r]（其中 0 <= l <= r < n）的 成本 定义为：
cost(l, r) = nums[l] - nums[l + 1] + ... + nums[r] * (−1)r − l
你的任务是将 nums 分割成若干子数组，使得所有子数组的成本之和 最大化，并确保每个元素 正好 属于一个子数组。
具体来说，如果 nums 被分割成 k 个子数组，且分割点为索引 i1, i2, ..., ik − 1（其中 0 <= i1 < i2 < ... < ik - 1 < n - 1），则总成本为：
cost(0, i1) + cost(i1 + 1, i2) + ... + cost(ik − 1 + 1, n − 1)
返回在最优分割方式下的子数组成本之和的最大值。
注意：如果 nums 没有被分割，即 k = 1，则总成本即为 cost(0, n - 1)。
示例 1：
输入： nums = [1,-2,3,4]
输出： 10
解释：
一种总成本最大化的方法是将 [1, -2, 3, 4] 分割成子数组 [1, -2, 3] 和 [4]。总成本为 (1 + 2 + 3) + 4 = 10。
示例 2：
输入： nums = [1,-1,1,-1]
输出： 4
解释：
一种总成本最大化的方法是将 [1, -1, 1, -1] 分割成子数组 [1, -1] 和 [1, -1]。总成本为 (1 + 1) + (1 + 1) = 4。
示例 3：
输入： nums = [0]
输出： 0
解释：
无法进一步分割数组，因此答案为 0。
示例 4：
输入： nums = [1,-1]
输出： 2
解释：
选择整个数组，总成本为 1 + 1 = 2，这是可能的最大成本。
提示：
1 <= nums.length <= 105-109 <= nums[i] <= 109原站题解
java 解法, 执行用时: 16 ms, 内存消耗: 59.3 MB, 提交时间: 2024-06-27 22:42:21
public class Solution {
public long maximumTotalCost(int[] a) {
int n = a.length;
long[][] f = new long[n + 1][2];
for (int i = n - 1; i >= 0; i--) {
f[i][0] = f[i + 1][1] + a[i];
f[i][1] = Math.max(f[i + 1][1] + a[i], f[i + 1][0] - a[i]);
}
return f[0][0];
}
public long maximumTotalCost2(int[] a) {
int n = a.length;
long[][] memo = new long[n][2];
for (long[] row : memo) {
Arrays.fill(row, Long.MIN_VALUE);
}
return dfs(0, 0, a, memo);
}
private long dfs(int i, int j, int[] a, long[][] memo) {
if (i == a.length) {
return 0;
}
if (memo[i][j] != Long.MIN_VALUE) { // 之前计算过
return memo[i][j];
}
return memo[i][j] = Math.max(dfs(i + 1, 1, a, memo) + a[i],
dfs(i + 1, j ^ 1, a, memo) + (j == 0 ? a[i] : -a[i]));
}
}
golang 解法, 执行用时: 55 ms, 内存消耗: 10.1 MB, 提交时间: 2024-06-27 22:41:36
func maximumTotalCost(a []int) int64 {
n := len(a)
f := make([][2]int, n+1)
for i := n - 1; i >= 0; i-- {
f[i][0] = f[i+1][1] + a[i]
f[i][1] = max(f[i+1][1]+a[i], f[i+1][0]-a[i])
}
return int64(f[0][0])
}
func maximumTotalCost1(a []int) int64 {
n := len(a)
memo := make([][2]int, n)
for i := range memo {
memo[i] = [2]int{math.MinInt, math.MinInt}
}
var dfs func(int, int) int
dfs = func(i, j int) int {
if i == n {
return 0
}
p := &memo[i][j]
if *p != math.MinInt { // 之前计算过
return *p
}
res := dfs(i+1, 1) + a[i] // 分割
r := dfs(i+1, j^1) // 不分割
if j == 0 {
r += a[i]
} else {
r -= a[i]
}
res = max(res, r)
*p = res // 记忆化
return res
}
return int64(dfs(0, 0))
}
cpp 解法, 执行用时: 87 ms, 内存消耗: 83.3 MB, 提交时间: 2024-06-27 22:40:55
class Solution {
public:
long long maximumTotalCost(vector<int>& a) {
int n = a.size();
vector<array<long long, 2>> f(n + 1);
for (int i = n - 1; i >= 0; i--) {
f[i][0] = f[i + 1][1] + a[i];
f[i][1] = max(f[i + 1][1] + a[i], f[i + 1][0] - a[i]);
}
return f[0][0];
}
long long maximumTotalCost2(vector<int>& a) {
int n = a.size();
vector<array<long long, 2>> memo(n, {LLONG_MIN, LLONG_MIN});
auto dfs = [&](auto&& dfs, int i, int j) -> long long {
if (i == n) {
return 0;
}
auto& res = memo[i][j]; // 注意这里是引用
if (res != LLONG_MIN) { // 之前计算过
return res;
}
return res = max(dfs(dfs, i + 1, 1) + a[i],
dfs(dfs, i + 1, j ^ 1) + (j == 0 ? a[i] : -a[i]));
};
return dfs(dfs, 0, 0);
}
};
python3 解法, 执行用时: 685 ms, 内存消耗: 281.9 MB, 提交时间: 2024-06-27 22:40:24
class Solution:
def maximumTotalCost(self, a: List[int]) -> int:
@cache # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
def dfs(i: int, j: int) -> int:
if i == len(a):
return 0
return max(dfs(i + 1, 1) + a[i],
dfs(i + 1, j ^ 1) + (-a[i] if j else a[i]))
return dfs(0, 0)
def maximumTotalCost2(self, a: List[int]) -> int:
n = len(a)
f = [[0, 0] for _ in range(n + 1)]
for i in range(n - 1, -1, -1):
f[i][0] = f[i + 1][1] + a[i]
f[i][1] = max(f[i + 1][1] + a[i], f[i + 1][0] - a[i])
return f[0][0]