Medium

题目描述

给你一个下标从 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 <= nums.length <= 105
  • 1 <= nums[i], x <= 106

解题思路

这是一道动态规划题目。关键在于理解奇偶性切换的代价和状态设计。

思路分析：

由于我们需要考虑奇偶性的变化，可以设计状态 dp[i][parity] 表示访问到位置 i，且最后访问的元素奇偶性为 parity 时的最大得分。但这样空间复杂度较高。

更优的方法是使用两个变量分别记录当前以奇数和偶数结尾的最大得分：

  • odd：以奇数结尾的最大得分
  • even：以偶数结尾的最大得分

对于每个位置 i，我们有两种选择：

  1. 如果 nums[i] 是奇数：
    • 从奇数位置转移过来：odd + nums[i]
    • 从偶数位置转移过来：even + nums[i] - x（需要扣除奇偶性切换的代价）
  2. 如果 nums[i] 是偶数：
    • 从偶数位置转移过来：even + nums[i]
    • 从奇数位置转移过来：odd + nums[i] - x

初始状态根据 nums[0] 的奇偶性设置，另一个状态设为负无穷（表示不可达）。

最终答案是 max(odd, even)。

时间复杂度： O(n)，只需遍历一次数组
空间复杂度： O(1)，只使用常数额外空间

代码实现

class Solution {
public:
    long long maxScore(vector<int>& nums, int x) {
        int n = nums.size();
        long long odd, even;
        
        if (nums[0] % 2 == 0) {
            even = nums[0];
            odd = nums[0] - x;
        } else {
            odd = nums[0];
            even = nums[0] - x;
        }
        
        for (int i = 1; i < n; i++) {
            if (nums[i] % 2 == 0) {
                even = max(even + nums[i], odd + nums[i] - x);
            } else {
                odd = max(odd + nums[i], even + nums[i] - x);
            }
        }
        
        return max(odd, even);
    }
};

class Solution:
    def maxScore(self, nums: List[int], x: int) -> int:
        n = len(nums)
        
        if nums[0] % 2 == 0:
            even = nums[0]
            odd = nums[0] - x
        else:
            odd = nums[0]
            even = nums[0] - x
        
        for i in range(1, n):
            if nums[i] % 2 == 0:
                even = max(even + nums[i], odd + nums[i] - x)
            else:
                odd = max(odd + nums[i], even + nums[i] - x)
        
        return max(odd, even)

public class Solution {
    public long MaxScore(int[] nums, int x) {
        int n = nums.Length;
        long odd, even;
        
        if (nums[0] % 2 == 0) {
            even = nums[0];
            odd = nums[0] - x;
        } else {
            odd = nums[0];
            even = nums[0] - x;
        }
        
        for (int i = 1; i < n; i++) {
            if (nums[i] % 2 == 0) {
                even = Math.Max(even + nums[i], odd + nums[i] - x);
            } else {
                odd = Math.Max(odd + nums[i], even + nums[i] - x);
            }
        }
        
        return Math.Max(odd, even);
    }
}

var maxScore = function(nums, x) {
    const n = nums.length;
    let evenMax = nums[0] % 2 === 0 ? nums[0] : nums[0] - x;
    let oddMax = nums[0] % 2 === 1 ? nums[0] : nums[0] - x;
    
    for (let i = 1; i < n; i++) {
        if (nums[i] % 2 === 0) {
            evenMax = Math.max(evenMax + nums[i], oddMax + nums[i] - x);
        } else {
            oddMax = Math.max(oddMax + nums[i], evenMax + nums[i] - x);
        }
    }
    
    return Math.max(evenMax, oddMax);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)只需遍历数组一次
空间复杂度O(1)只使用常数额外空间

相关题目