一、题目
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、原题链接
二、解题报告
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**9
f0 = nums[0] if f1 < 0 else -10**9
for 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]);
};
