题目
给你一个下标从 0 开始的整数数组 nums 和一个正整数 x 。
你 一开始 在数组的位置 0 处，你可以按照下述规则访问数组中的其他位置：
如果你当前在位置 i ，那么你可以移动到满足 i < j 的 任意 位置 j 。
对于你访问的位置 i ，你可以获得分数 nums[i] 。
如果你从位置 i 移动到位置 j 且 nums[i] 和 nums[j] 的 奇偶性 不同，那么你将失去分数 x 。
请你返回你能得到的 最大 得分之和。
注意 ，你一开始的分数为 nums[0] 。
示例 1：
输入：nums = [2,3,6,1,9,2], x = 5
输出：13
解释：我们可以按顺序访问数组中的位置：0 -> 2 -> 3 -> 4 。
对应位置的值为 2 ，6 ，1 和 9 。因为 6 和 1 的奇偶性不同，所以下标从 2 -> 3 让你失去 x = 5 分。
总得分为：2 + 6 + 1 + 9 - 5 = 13 。
示例 2：
输入：nums = [2,4,6,8], x = 3
输出：20
解释：数组中的所有元素奇偶性都一样，所以我们可以将每个元素都访问一次，而且不会失去任何分数。
总得分为：2 + 4 + 6 + 8 = 20 。
提示：
- $2 <= nums.length <= 10^5$
- $1 <= nums[i], x <= 10^6$
审题
每一步有多个选择，到有每一步都有case需要处理进一步求最优解，动态规划！！！
那么咱们先从深度优先搜索 + 剪枝的方式入手。枚举全部case，并求最大值。
深度优先搜索 + 记忆化
$ T_n=O(n) \ C_n=O(n)$
子问题：在下标[i, n - 1]中选择一个子序列，其第一个数的奇偶性为same （也就是摸2的结果为same）时的最大得分，对应于dfs(i,same)。
- 如过
v mod 2 != same，由于奇偶性不一致，有负向收益（减去x），可以不选（不选可能是最优解的路线），那么：问题进一步变成：在下标[i+1, n - 1]中选择一个子序列，其第一个数的奇偶性为same（也就是摸2的结果为same）时的最大得分。即：dfs(i,same) = dfs(i+1, same) - 如过
v mod 2 = same，奇偶性一致，收益是正向的，必须选择。那么有两个case:- case1: 在下标
[i+1, n - 1]中选择一个子序列，其第一个数的奇偶性为same（也就是摸2的结果为same）时的最大得分。即：dfs(i,same) = dfs(i+1, same) + v - case2: 在下标
[i+1, n - 1]中选择一个子序列，其第一个数的奇偶性为same ^ 1（奇偶性相反的case）时的最大得分。即：dfs(i,same) = dfs(i+1, same ^ 1) + v - 这两种取最优解，得到
dfs(i,same)：dfs(i,same) = max(dfs(i+1, same) + v,dfs(i+1, same ^ 1)) + v
- case1: 在下标
递归边界：dfs(n，same) = 0，因为n没有后续元素了。
递归入口：dfs(0, nums[0] mod 2)，是最终的答案（递归归到了dfs(0, nums[0] mod 2)。
记忆化：将dfs(i,same)的结果用数组存起来 memo[n][2]。
代码实现
class Solution {
public long maxScore(int[] nums, int x) {
int n = nums.length;
long[][] memo = new long[n][2];
for (int i = 0; i < n; i++) {
Arrays.fill(memo[i], -1);
}
return dfs(0, nums[0] % 2, nums, x, memo);
}
private long dfs(int i, int same, int[] nums, int x, long[][] memo) {
if (i == nums.length) {
return 0;
}
if (memo[i][same] != -1) {
return memo[i][same];
}
if (nums[i] % 2 != same) {
// pass nums[i] try find max score
return memo[i][same] = dfs(i + 1, same, nums, x, memo);
}
long chooseSame = dfs(i + 1, same, nums, x, memo);
long chooseNotSame = dfs(i + 1, same ^ 1, nums, x, memo);
return memo[i][same] = Math.max(chooseSame, chooseNotSame - x) + nums[i];
}
}
动态规划
$ T_n=O(n) \ C_n=O(n)$
（实现递归的归流程）
定义dp[i][same] 表示在下标[i,n-1]中选一个子序列，起第一个数字的奇偶性为same（也就是摸2的结果为same）时的最大得分。
设 v = nums[i]，相应的递推式如下：
$$
dp[i][same] =
\begin{cases}
dp[i + 1][same] & v % 2 \neq same, \
max(dp[i + 1][same], dp[i + 1][same⌖1] - x) + v & v % 2 = same.
\end{cases}
$$
代码实现
class Solution {
public long maxScore(int[] nums, int x) {
int n = nums.length;
long[][] dp = new long[n + 1][2];
for (int i = n - 1; i >= 0; i--) {
int v = nums[i];
int same = v % 2;
dp[i][same ^ 1] = dp[i + 1][same ^ 1];// case 跳过 nums[i]
// case 可以选，要么无损，要么损失 x
dp[i][same] = Math.max(dp[i + 1][same], dp[i + 1][same ^ 1] - x) + v;
}
return dp[0][nums[0] % 2];
}
}
动态规划 优化
$ T_n=O(n) \ C_n=O(1)$
优化空间复杂度
注意到，状态转移只和相邻元素有关系，我们可以以除掉各个位置的奇偶情况的最优解，只用一个长度为2的数组来复用。
状态转移方程改为：
$$
dp[same] = max(dp[same],dp[same ⌖ 1] - x) + v , v % 2 = same
$$
v % 2 != same 无需计算，因为去掉第一维度，化简后是恒等式。
初始值：dp[same] = 0，same = nums[0] % 2
class Solution {
public long maxScore(int[] nums, int x) {
int n = nums.length;
long[] dp = new long[2];
for (int i = n - 1; i >= 0; i--) {
int v = nums[i];
int same = v % 2;
// case 可以选，要么无损，要么损失 x
dp[same] = Math.max(dp[same], dp[same ^ 1] - x) + v;
}
return dp[nums[0] % 2];
}
}
// n & 1 = n % 2，使用 & 速度更快！！！
class Solution {
public long maxScore(int[] nums, int x) {
int n = nums.length;
long[] dp = new long[2];
for (int i = n - 1; i >= 0; i--) {
int v = nums[i];
int same = v & 1;
// case 可以选，要么无损，要么损失 x
dp[same] = Math.max(dp[same], dp[same ^ 1] - x) + v;
}
return dp[nums[0] & 1];
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
