记忆化搜索#
表示：当前考虑到下标 ，且上一个选中的数奇偶性为 时，从 到 能获得的最大额外分数。
此时，对于 ，它的奇偶性为 ：
- （奇偶性相同）
- 选：既然奇偶性相同，不需要减 。那么选了肯定比不选好，因为 且没有改变后续的奇偶性
- 决策：
- （奇偶性不同）
- 不选：维持现状，继续往后看。结果为
- 选：获得了 的分数，但是要扣除 ，且状态改变了，从此往后”上一个数”的奇偶性变成了 （即 ）
- 决策：
所以整体的递归思路应该是：
int[] nums;
long[][] memo;
int x;
public long maxScore(int[] nums, int x) {
this.nums = nums;
this.x = x;
int n = nums.length;
memo = new long[n][2];
for (long[] row : memo) {
Arrays.fill(row, -1);
}
return dfs(0, nums[0] % 2);
}
private long dfs(int i, int j) {
if (i == nums.length) {
return 0;
}
if (memo[i][j] != -1) {
return memo[i][j];
}
int curr = nums[i] & 1;
if (curr == j) {
// 奇偶性相同必选
return memo[i][j] = dfs(i + 1, j) + nums[i];
} else {
// 奇偶性不同，选或不选
return memo[i][j] = Math.max(dfs(i + 1, j), nums[i] - x + dfs(i + 1, j ^ 1));
}
}递推#
理解了上面的状态转移后，递推就非常简单了：
- 代表在 中以偶数开头的子序列的最大得分；
- 代表在 中以奇数开头的子序列的最大得分。
public long maxScore(int[] nums, int x) {
int n = nums.length;
long[][] f = new long[n + 1][2];
for (int i = n - 1; i >= 0; --i) {
int v = nums[i];
int r = v & 1;
// 相同必选
f[i][r] = v + f[i + 1][r];
// 不同，选或不选
f[i][r ^ 1] = Math.max(f[i + 1][r ^ 1], f[i + 1][r] + v - x);
}
return f[0][nums[0] % 2];
}迭代 DP#
倒推#
在递推中，我们只会访问 的值，所以没有必要全部维护。
public long maxScore(int[] nums, int x) {
long[] f = new long[2];
for (int i = nums.length - 1; i >= 0; --i) {
int v = nums[i];
int r = v & 1;
// 不同，选或不选
f[r ^ 1] = Math.max(f[r ^ 1], f[r] + v - x);
// 相同必选
f[r] = v + f[r];
}
return f[nums[0] % 2];
}注意：这里的更新顺序不能改变，即必须先更新 后更新 （也可以用一个临时变量 先占位 ）。
正推#
由于第一个数必须选，因此正推的逻辑可能会更清晰。
正推逻辑：当前数 的奇偶性为
- 代表以偶数结尾的子序列最大得分， 代表以奇数结尾的子序列最大得分
- 只能更新 ，因为选了数 后，结尾奇偶性一定为
- 保持不变，因为当前数 无法改变以异号结尾的子序列的最大分数
状态转移方程：
public long maxScore(int[] nums, int x) {
long[] f = new long[2];
Arrays.fill(f, Long.MIN_VALUE / 2); // 防止减x溢出
f[nums[0] & 1] = nums[0];
for (int i = 1; i < nums.length; ++i) {
int v = nums[i];
int r = v & 1;
f[r] = Math.max(f[r] + v, f[r ^ 1] - x + v);
}
return Math.max(f[0], f[1]);
}