本文主要是介绍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. 访问数组中的位置使分数最大的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
