目标
给你一个下标从 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
思路
给定一个数组 nums 与 正整数 x，从下标 0 开始，允许从任意位置 i 开始向后访问位置 j，如果nums[i] 与 nums[j] 的奇偶性相同，则可以获得 nums[j] 分，否则获得 nums[j] - x 分。求能够获得的分数总和的最大值。
刚开始就想到要从后向前，自底向上动态规划，如果当前的奇偶性与与后面的奇偶性相同就累加，否则就将后面的值减去x。接着又想到并不是要每一个节点都要访问，如果节点没有访问奇偶性和谁比较呢？并且后面的得分取决于前一个元素的奇偶性，考虑到昨天的题 子序列最大优雅度，觉得可能方向又错了。
于是就尝试贪心算法，从下标0开始，执行while循环，如果后面的元素奇偶性与之相同，直接累加。对于奇偶性不同的，我们可以考虑累加或者跳过。这样问题就变成了从这个新位置开始向后能获取的最大分数。注意新的位置奇偶性发生了变化。
这么一想问题又变成记忆化搜索了，于是就可以转换为递推/动态规划问题。
// todo 转换为动态规划的写法
代码
/**
* @date 2024-06-14 8:43
*/
public class MaxScore2786 {
public long maxScore(int[] nums, int x) {
int n = nums.length;
long[][] mem = new long[n + 1][2];
for (int i = 0; i < mem.length; i++) {
mem[i] = new long[]{Integer.MIN_VALUE, Integer.MIN_VALUE};
}
long res = nums[0];
int flag = nums[0] % 2;
int i = 1;
while (i < n && nums[i] % 2 == flag) {
res += nums[i];
i++;
}
res += Math.max(0, maxScore(nums, x, i, flag, mem));
return res;
}
public long maxScore(int[] nums, int x, int start, int preFlag, long[][] mem) {
int n = nums.length;
if (start >= n) {
return 0;
}
// 如果选择该节点
int flag = nums[start] % 2;
long select = nums[start];
if (preFlag != flag) {
select -= x;
}
int i = start + 1;
while (i < n && nums[i] % 2 == flag) {
select += nums[i];
i++;
}
if (mem[i][flag] == Integer.MIN_VALUE) {
mem[i][flag] = maxScore(nums, x, i, flag, mem);
}
select += Math.max(0, mem[i][flag]);
// 如果跳过该节点
if (mem[start + 1][preFlag] == Integer.MIN_VALUE) {
mem[start + 1][preFlag] = maxScore(nums, x, start + 1, preFlag, mem);
}
return Math.max(select, mem[start + 1][preFlag]);
}
}
性能
