Leetcode.2786 访问数组中的位置使分数最大

题目链接

Leetcode.2786 访问数组中的位置使分数最大 rating : 1732

题目描述

给你一个下标从 $0$ 开始的整数数组 $n u m s$ 和一个正整数 $x$ 。

你 一开始 在数组的位置 $0$ 处，你可以按照下述规则访问数组中的其他位置：

如果你当前在位置 $i$ ，那么你可以移动到满足 $i < j$ 的任意位置 $j$ 。
对于你访问的位置 $i$ ，你可以获得分数 $n u m s [i]$ 。
如果你从位置 $i$ 移动到位置 $j$ 且 $n u m s [i]$ 和 $n u m s [j]$ 的 奇偶性 不同，那么你将失去分数 $x$ 。

请你返回你能得到的最大得分之和。

注意，你一开始的分数为 $n u m s [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 。

提示：

$\leq nums.length \leq 10^5$
$\leq nums[i], x \leq 10^6$

解法一：动态规划

定义 $f [i] [j]$ 为前 $n u m s$ 前 $i$ 个元素，最后一个元素是奇数或者偶数 $(j = 0, 是偶数; j = 1, 是奇数)$ 的最大分数和。注意：最后一个元素不一定是第 $i$ 个元素。

对于第 $i$ 个元素 $n u m s [i]$ ，用 $k$ 表示它的奇偶性质：

$f[i-1][k\ xor\ 1] - x) + nums[i]$
$f[i][k\ xor\ 1] = f[i-1][k\ xor\ 1]$

由于 $f$ 默认下标是从 $1$ 开始的，而 $n u m s$ 是从 $0$ 开始的，所以需要做下转换：

$f[i-1][k\ xor\ 1] - x) + nums[i - 1]$
$f[i][k\ xor\ 1] = f[i-1][k\ xor\ 1]$

注意： $f$ 需要初始化为一个相对较小的数字，因为 $f[i-1][k\ xor\ 1] - x$ 是有可能小于 $0$ 的，如果 $f$ 全部初始化为 $0$ ，并且此时恰好 $f [i - 1] [k] = 0$ ，最终就会得到一个错误的结果。本来这里的答案应该是 $f[i-1][k\ xor\ 1] - x + nums[i - 1]$ ，最终却变成了 $f [i] [k] = 0 + n u m s [i - 1]$ 。最终结果就会比标准答案偏大。

比如这个用例：

在这里插入图片描述

时间复杂度： $O (n)$

C++代码：


using LL = long long;class Solution {
public:long long maxScore(vector<int>& nums, int x) {int n = nums.size();vector<vector<LL>> f(n + 1, vector<LL>(2, -1e18));f[1][nums[0] & 1] = nums[0];for(int i = 2;i <= n;i++){int k = (nums[i - 1] & 1);f[i][k] = max(f[i - 1][k], f[i - 1][k ^ 1] - x) + nums[i - 1];f[i][k ^ 1] = f[i - 1][k ^ 1];}return max(f[n][0], f[n][1]);}
};

解法二：动态规划 + 一维空间

我们注意到 $f [i] [k]$ 实际只会依赖于 $f [i - 1] [k]$ 和 $1][k\ xor\ 1]$ ，所以我们可以直接降维，使用两个变量来模拟。