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

难度: 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 <= 10⁵
1 <= nums[i], x <= 10⁶

Submission

运行时间: 166 ms

内存: 30.7 MB

class Solution:
    def maxScore(self, nums: List[int], x: int) -> int:
        oddmax = evenmax = 0
        if nums[0] & 1:
            oddmax = nums[0]
            evenmax = -x
        else:
            evenmax = nums[0]
            oddmax = -x
        for y in nums[1:]:
            if y & 1:
                oddmax = max(oddmax + y, evenmax + y - x)
            else:
                evenmax = max(evenmax + y, oddmax + y - x)
        return max(oddmax, evenmax)

Explain

本题解采用动态规划的思路来计算最大得分。定义两个变量 oddmax 和 evenmax，分别存储到达当前位置时，如果当前位置是奇数或偶数时能得到的最大分数。初始化时，根据 nums[0] 的奇偶性来设定 oddmax 和 evenmax 的初始值。遍历数组的每一个元素，根据当前元素的奇偶性更新 oddmax 和 evenmax。如果当前元素是奇数，则 oddmax 可以由前一个奇数直接加上当前值或由前一个偶数转换而来（减去x分）。同理，如果当前元素是偶数，则 evenmax 可以由前一个偶数直接加或由前一个奇数转换而来。最后，返回 oddmax 和 evenmax 中的较大值作为最终答案。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def maxScore(self, nums: List[int], x: int) -> int:
        oddmax = evenmax = 0
        # 初始化奇数和偶数最大值
        if nums[0] & 1:
            oddmax = nums[0]
            evenmax = -x
        else:
            evenmax = nums[0]
            oddmax = -x
        # 遍历数组中的每个数，更新奇偶最大得分
        for y in nums[1:]:
            if y & 1:
                oddmax = max(oddmax + y, evenmax + y - x)  # 若当前数是奇数
            else:
                evenmax = max(evenmax + y, oddmax + y - x)  # 若当前数是偶数
        return max(oddmax, evenmax)  # 返回最大得分

Explore

动态规划是解决这种类型问题的一个有效方法，因为它能够处理决策过程中的状态转移。具体来说，每次访问数组中的一个元素时，你都面临一个选择：根据当前元素的奇偶性来更新你的得分。动态规划允许我们通过将大问题分解成相似的子问题，并保存这些子问题的解（这里是奇数和偶数的最大分数），从而有效地解决问题。这种方法特别适合于这个问题，因为每一步的最优决策依赖于前一步的状态，而不是从头到当前位置的完整历史。

在动态规划的实现中，oddmax 和 evenmax 每次只根据前一个状态（即上一步的 oddmax 和 evenmax）来更新。这是通过在每一步中重新计算 these 两个变量并基于当前元素的奇偶性来决定如何更新来实现的。这种方法确保了每个状态的更新仅依赖于直接前驱的状态，避免了早期状态的直接影响，从而保持了状态转移的正确性和效率。

在这个问题中，-x 代表了一种惩罚或成本，当你从一个奇数状态转移到一个偶数状态或反之时会扣除这个值。在初始化时，如果第一个元素是奇数，我们将 oddmax 初始化为该元素的值，因为这是一个有效的起点，而将 evenmax 设置为 -x，表示如果我们非要从一个奇数状态转为偶数状态，我们需要付出的代价。反之亦然。这种初始化方法反映了从一个不存在的相反状态转换到当前状态的代价，是问题逻辑的一部分，确保了动态规划在开始阶段就能正确地评估各种转换的成本。

是的，更新表达式考虑了所有必要的状态转移。对于每个新的元素，根据其奇偶性，我们考虑了保持当前状态（即奇数加奇数或偶数加偶数）或改变当前状态（即奇数加偶数或偶数加奇数，并扣除相应的成本 x）。这两种情况都被涵盖在更新 oddmax 和 evenmax 的逻辑中，确保了无论当前元素是奇数还是偶数，都能得到正确的最大分数计算。