LeetCode每日一题

题目来源：力扣（LeetCode）

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

动态规划 数组

题目描述

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

题解

动态规划

从左到右遍历数组，遍历到一个元素 $e$ 时，如果移动到此位置，那么能获取的最大分数取决于：

上一次移动到的元素为奇数且得分最大值 $odd$
上一次移动到的元素为偶数且得分最大值 $even$

即移动到当前位置可以获得的最大得分 $now$ 等于:

在当前元素为奇数时：$now=max(odd+e,even+e-x)$
在当前元素为偶数时：$now=max(odd+e-x,even+e)$

将最大得分之和 $score$ 更新为：

$score=max(score,now)$

class Solution:
    def maxScore(self, nums: List[int], x: int) -> int:
        # 从下标0处开始
        res = nums[0]  # 取第一个元素的得分
        dp = [-inf, -inf]  # 维护一个长度为2的数组dp来保存[even,odd]的值
        dp[nums[0] % 2] = nums[0]  # 根据第一个元素的奇偶性更新even或odd
        
        # 从左到右遍历更新dp
        for i in range(1, len(nums)):
            parity = nums[i] % 2  # 获取当前元素奇偶性
            cur = max(dp[parity] + nums[i], dp[1 - parity] + nums[i] - x)  # 代入求当前得分now的公式
            res = max(res, cur)  # 更新最大得分和
            dp[parity] = max(dp[parity], cur)  # 更新even或odd
        return res

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 是数组 $nums$ 的长度。
空间复杂度：$O(1)$。