来源第 403 场周赛 Q3难度中等分数1846
题目描述
给你一个长度为 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
解法
方法一：记忆化搜索
思考
划分后每段按正负交替计分，段首必须为正。枚举全部切法是指数的。
当前位置能否取负，只取决于上一个数是否已经取负：取负后下一位必须为正。
记忆化 \(dfs(i,j)\)： \(j=1\) 表示可以取负。始终尝试 \(nums[i]+dfs(i+1,1)\)，若允许再与 \(-nums[i]+dfs(i+1,0)\) 取大。
根据题目描述，如果当前数没取反，那么下一个可以取反，也可以不取反；如果当前数取反了，那么下一个只能不取反。
因此，我们定义一个函数 \(\textit{dfs}(i, j)\)，表示从第 \(i\) 个数开始，第 \(i\) 个数是否能取反，其中 \(j\) 表示第 \(i\) 个数是否取反。如果 \(j = 0\)，表示第 \(i\) 个数不能取反，否则可以取反。答案为 \(\textit{dfs}(0, 0)\)。
函数 \(dfs(i, j)\) 的执行过程如下：
- 如果 \(i \geq \textit{len}(nums)\)，表示已经遍历完了数组，返回 \(0\)；
- 否则，第 \(i\) 个数可以不取反，此时答案为 \(nums[i] + \textit{dfs}(i + 1, 1)\)；如果 \(j = 1\)，表示第 \(i\) 个数可以取反，此时答案为 \(\max(\textit{dfs}(i + 1, 0) - nums[i])\)。我们取两者的最大值即可。
为了避免重复计算，我们可以使用记忆化搜索，将已经计算过的结果保存起来。
时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是数组 \(nums\) 的长度。
1
2
3
4
5
6
7
8
9
10
11
12 | class Solution:
def maximumTotalCost(self, nums: List[int]) -> int:
@cache
def dfs(i: int, j: int) -> int:
if i >= len(nums):
return 0
ans = nums[i] + dfs(i + 1, 1)
if j == 1:
ans = max(ans, -nums[i] + dfs(i + 1, 0))
return ans
return dfs(0, 0)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | class Solution {
private Long[][] f;
private int[] nums;
private int n;
public long maximumTotalCost(int[] nums) {
n = nums.length;
this.nums = nums;
f = new Long[n][2];
return dfs(0, 0);
}
private long dfs(int i, int j) {
if (i >= n) {
return 0;
}
if (f[i][j] != null) {
return f[i][j];
}
f[i][j] = nums[i] + dfs(i + 1, 1);
if (j == 1) {
f[i][j] = Math.max(f[i][j], -nums[i] + dfs(i + 1, 0));
}
return f[i][j];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution {
public:
long long maximumTotalCost(vector<int>& nums) {
int n = nums.size();
long long f[n][2];
fill(f[0], f[n], LLONG_MIN);
auto dfs = [&](this auto&& dfs, int i, int j) -> long long {
if (i >= n) {
return 0;
}
if (f[i][j] != LLONG_MIN) {
return f[i][j];
}
f[i][j] = nums[i] + dfs(i + 1, 1);
if (j) {
f[i][j] = max(f[i][j], -nums[i] + dfs(i + 1, 0));
}
return f[i][j];
};
return dfs(0, 0);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | func maximumTotalCost(nums []int) int64 {
n := len(nums)
f := make([][2]int64, n)
for i := range f {
f[i] = [2]int64{-1e18, -1e18}
}
var dfs func(int, int) int64
dfs = func(i, j int) int64 {
if i >= n {
return 0
}
if f[i][j] != -1e18 {
return f[i][j]
}
f[i][j] = int64(nums[i]) + dfs(i+1, 1)
if j > 0 {
f[i][j] = max(f[i][j], int64(-nums[i])+dfs(i+1, 0))
}
return f[i][j]
}
return dfs(0, 0)
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | function maximumTotalCost(nums: number[]): number {
const n = nums.length;
const f: number[][] = Array.from({ length: n }, () => Array(2).fill(-Infinity));
const dfs = (i: number, j: number): number => {
if (i >= n) {
return 0;
}
if (f[i][j] !== -Infinity) {
return f[i][j];
}
f[i][j] = nums[i] + dfs(i + 1, 1);
if (j) {
f[i][j] = Math.max(f[i][j], -nums[i] + dfs(i + 1, 0));
}
return f[i][j];
};
return dfs(0, 0);
}
|
方法二：动态规划
思考
方法一从末尾填了一张线性表。两个选择还可以再压成两个滚动值。
\(f\) 为当前不取负的最大， \(g\) 为取负的最大。不取负时前一位任意，取负时前一位必须不取负。
转移 \(f=\max(f,g)+x\)， \(g=f_{old}-x\)。答案为 \(\max(f,g)\)，额外空间降为常数。
我们可以将方法一中的线性表压成两个滚动值。
定义 \(f\) 和 \(g\) 为两个状态，其中 \(f\) 表示当前数不取反的最大值，而 \(g\) 表示当前数取反的最大值。
遍历数组 \(nums\)，对于第 \(i\) 个数，我们可以根据 \(f\) 和 \(g\) 的状态更新 \(f\) 和 \(g\) 的值：
- 如果当前数不取反，那么 \(f\) 的值为 \(\max(f, g) + x\)，表示当前数不取反，那么前一个数可以取反或不取反；
- 如果当前数取反，那么 \(g\) 的值为 \(f - x\)，表示当前数取反，那么前一个数不能取反
最终答案为 \(\max(f, g)\)。
时间复杂度 \(O(n)\)，其中 \(n\) 是数组 \(nums\) 的长度。空间复杂度 \(O(1)\)。
| class Solution:
def maximumTotalCost(self, nums: List[int]) -> int:
f, g = -inf, 0
for x in nums:
f, g = max(f, g) + x, f - x
return max(f, g)
|
1
2
3
4
5
6
7
8
9
10
11
12 | class Solution {
public long maximumTotalCost(int[] nums) {
long f = Long.MIN_VALUE / 2, g = 0;
for (int x : nums) {
long ff = Math.max(f, g) + x;
long gg = f - x;
f = ff;
g = gg;
}
return Math.max(f, g);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12 | class Solution {
public:
long long maximumTotalCost(vector<int>& nums) {
long long f = LLONG_MIN / 2, g = 0;
for (int x : nums) {
long long ff = max(f, g) + x, gg = f - x;
f = ff;
g = gg;
}
return max(f, g);
}
};
|
| func maximumTotalCost(nums []int) int64 {
f, g := math.MinInt64/2, 0
for _, x := range nums {
f, g = max(f, g)+x, f-x
}
return int64(max(f, g))
}
|
| function maximumTotalCost(nums: number[]): number {
let [f, g] = [-Infinity, 0];
for (const x of nums) {
[f, g] = [Math.max(f, g) + x, f - x];
}
return Math.max(f, g);
}
|
方法三：动态规划
思考
划分后每段按正负交替计分，段首必须为正。枚举全部切法是指数的，而 \(n\le 10^5\)。
当前位置能否取负，只取决于后面的后缀：取正之后下一位可以取负，取负之后下一位必须为正。
按这个递推搜索时仍会先调用下一位置再返回，调用链深度为 \(n\)，栈会溢出。
从末尾往前走时，下一位置已经就绪。令 \(f[i][j]\) 为从 \(i\) 起的最优得分， \(j=1\) 表示 \(\textit{nums}[i]\) 可以取负。我们从 \(i=n-1\) 填到 \(0\)，返回 \(f[0][0]\)。
如果当前数没有取负，下一个数既可以取负，也可以不取负；如果当前数取负了，下一个数只能不取负。
令 \(f[i][j]\) 表示从下标 \(i\) 开始的后缀能得到的最大得分，其中 \(j = 1\) 表示 \(\textit{nums}[i]\) 可以取负， \(j = 0\) 表示它必须保持为正。答案为 \(f[0][0]\)。数组末尾之后 \(f[n][0] = f[n][1] = 0\)。
下标 \(i\) 可以不取负，得分为 \(\textit{nums}[i] + f[i + 1][1]\)。当 \(j = 1\) 时还可以取负，得分为 \(-\textit{nums}[i] + f[i + 1][0]\)。 \(f[i][j]\) 取这些选择中的较大值。
我们从 \(i = n - 1\) 往前计算到 \(0\)。
时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是数组 \(\textit{nums}\) 的长度。
| class Solution:
def maximumTotalCost(self, nums: List[int]) -> int:
n = len(nums)
f = [[0, 0] for _ in range(n + 1)]
for i in range(n - 1, -1, -1):
for j in range(2):
ans = nums[i] + f[i + 1][1]
if j == 1:
ans = max(ans, -nums[i] + f[i + 1][0])
f[i][j] = ans
return f[0][0]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | class Solution {
public long maximumTotalCost(int[] nums) {
int n = nums.length;
long[][] f = new long[n + 1][2];
for (int i = n - 1; i >= 0; --i) {
for (int j = 0; j < 2; ++j) {
f[i][j] = nums[i] + f[i + 1][1];
if (j == 1) {
f[i][j] = Math.max(f[i][j], -nums[i] + f[i + 1][0]);
}
}
}
return f[0][0];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | class Solution {
public:
long long maximumTotalCost(vector<int>& nums) {
int n = nums.size();
vector<vector<long long>> f(n + 1, vector<long long>(2));
for (int i = n - 1; i >= 0; --i) {
for (int j = 0; j < 2; ++j) {
f[i][j] = nums[i] + f[i + 1][1];
if (j) {
f[i][j] = max(f[i][j], -nums[i] + f[i + 1][0]);
}
}
}
return f[0][0];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13 | func maximumTotalCost(nums []int) int64 {
n := len(nums)
f := make([][2]int64, n+1)
for i := n - 1; i >= 0; i-- {
for j := 0; j < 2; j++ {
f[i][j] = int64(nums[i]) + f[i+1][1]
if j == 1 {
f[i][j] = max(f[i][j], int64(-nums[i])+f[i+1][0])
}
}
}
return f[0][0]
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13 | function maximumTotalCost(nums: number[]): number {
const n = nums.length;
const f: number[][] = Array.from({ length: n + 1 }, () => Array(2).fill(0));
for (let i = n - 1; i >= 0; --i) {
for (let j = 0; j < 2; ++j) {
f[i][j] = nums[i] + f[i + 1][1];
if (j === 1) {
f[i][j] = Math.max(f[i][j], -nums[i] + f[i + 1][0]);
}
}
}
return f[0][0];
}
|