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

题目链接

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

题目描述

给你一个下标从 $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\le nums.length\le 10^5$
• $1\le nums[i],x\le 10^6$

解法一：动态规划

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

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

• $f[i][k]=max(f[i-1][k],f[i-1][kxor1]-x)+nums[i]$
• $f[i][kxor1]=f[i-1][kxor1]$

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

• $f[i][k]=max(f[i-1][k],f[i-1][kxor1]-x)+nums[i-1]$
• $f[i][kxor1]=f[i-1][kxor1]$

注意：$f$ 需要初始化为一个相对较小的数字，因为 $f[i-1][kxor1]-x$ 是有可能小于 $0$ 的，如果 $f$ 全部初始化为 $0$，并且此时恰好 $f[i-1][k]=0$，最终就会得到一个错误的结果 。本来这里的答案应该是 $f[i][k]=f[i-1][kxor1]-x+nums[i-1]$，最终却变成了 $f[i][k]=0+nums[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]$ 和 $f[i-1][kxor1]$，所以我们可以直接降维，使用两个变量来模拟。

时间复杂度：$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]);
    }
};

Python3代码：

class Solution:
    def maxScore(self, nums: List[int], x: int) -> int:
        n = len(nums)
        f = [-inf] * 2
        f[nums[0] & 1] = nums[0]

        for i in range(1, n):
            k = (nums[i] & 1)
            f[k] = max(f[k], f[k ^ 1] - x) + nums[i]
        
        return max(f[0], f[1])