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

本文主要是介绍LeetCode 2786. 访问数组中的位置使分数最大，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目

1、题目描述

给你一个下标从 0 开始的整数数组 nums 和一个正整数 x 。

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

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

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

注意 ，你一开始的分数为 nums[0] 。

2、接口描述

python3

 ​

class Solution:def maxScore(self, nums: List[int], x: int) -> int:

cpp

 ​

class Solution {
public:long long maxScore(vector<int>& nums, int x) {}
};

js

 ​

/*** @param {number[]} nums* @param {number} x* @return {number}*/
var maxScore = function(nums, x) {};

3、原题链接

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

---

二、解题报告

1、思路分析

不难写出O(N^2)的朴素dp

f[i]为前i元素以i结尾的最大收益

但是我们发现我们状态转移和奇偶性有关

我们并不关注前面状态具体的值，我们只关注奇偶性

而我们每次无非就是从前面某个奇数结尾或者偶数结尾转移

那我们不妨只记录奇偶结尾的最大收益，然后进行转移即可

这样状态转移就变成了O(1)的

2、复杂度

时间复杂度： O(N)空间复杂度：O(1)

3、代码详解

python3

 ​

class Solution:def maxScore(self, nums: List[int], x: int) -> int:n = len(nums)f1 = nums[0] if nums[0] & 1 else -10**9f0 = nums[0] if f1 < 0 else -10**9for i in range(1, n):if nums[i] & 1:f1 = max(f1, f0 + nums[i] - x, f1 + nums[i])else:f0 = max(f0, f0 + nums[i], f1 + nums[i] - x)return max(f0, f1)

cpp

 ​

using i64 = long long;
const i64 inf = 1e9;
auto _ = []{std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);return 0;
};
class Solution {
public:long long maxScore(vector<int>& nums, int x) {i64 f[2] { -inf, -inf };int n = nums.size();f[nums[0] & 1] = nums[0];for (int i = 1; i < n; i ++) {int j = nums[i] & 1;f[j] = max(f[j ^ 1] + nums[i] - x, f[j] + nums[i]);}return std::max(f[0], f[1]);}
};

js

 ​

/*** @param {number[]} nums* @param {number} x* @return {number}*/
var maxScore = function(nums, x) {let f = [-Infinity, -Infinity];f[nums[0] & 1] = nums[0];for (let i = 1; i < nums.length; i ++ ) {let j = nums[i] & 1;f[j] = Math.max(f[j], f[j ^ 1] + nums[i] - x, f[j] + nums[i]);}return Math.max(f[0], f[1]);
};

这篇关于LeetCode 2786. 访问数组中的位置使分数最大的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---