What is the main pattern to solve Visit Array Positions to Maximize Score?

The problem follows a state transition dynamic programming pattern where each dp[i] captures the maximum score at position i considering parity penalties.

How do I handle moves between numbers of different parity?

Subtract the given penalty x from your total score whenever a move crosses numbers of different parity in your DP state updates.

Can this problem be optimized from O(n^2) to O(n)?

Yes, by maintaining separate maximum scores for even and odd parity numbers, you can avoid iterating all previous indices and reduce redundant calculations.

What should I store in the DP array?

Store the maximum achievable score at each index considering moves from previous indices and parity penalties.

Are there edge cases to consider?

Yes, arrays where all numbers have the same parity allow full accumulation without penalties, and small arrays require careful initialization of dp[0].

#2786

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

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

给你一个下标从 0 开始的整数数组 nums 和一个正整数 x 。你一开始在数组的位置 0 处，你可以按照下述规则访问数组中的其他位置：如果你当前在位置 i ，那么你可以移动到满足 i 的任意位置 j 。对于你访问的位置 i ，你可以获得分数 nums[i] 。如果你从位置 i 移动…

数组动态规划

题目描述

给你一个下标从 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⁶

lightbulb

解题思路

方法一：动态规划

根据题目描述，我们可以得到以下结论：

从位置 $i$ 移动到位置 $j$ 时，如果 $nums[i]$ 和 $nums[j]$ 的奇偶性不同，那么会损失 $x$ 分；
从位置 $i$ 移动到位置 $j$ 时，如果 $nums[i]$ 和 $nums[j]$ 的奇偶性相同，那么不会损失分数。

因此，我们可以用一个长度为 $2$ 的数组 $f$ 来表示当前位置的奇偶性为 $0$ 和 $1$ 时的最大得分。初始时 $f$ 的值为 $-\infty$ ，然后我们再初始化 $f[nums[0] \& 1] = nums[0]$ ，表示初始位置的得分。

接下来，我们从位置 $1$ 开始遍历数组 $nums$ ，对于每个位置 $i$ 对应的值 $v$ ，我们更新 $f[v \& 1]$ 的值为 $f[v \& 1]$ 和 $f[v \& 1 \oplus 1] - x$ 的较大值再加上 $v$ ，即 $f[v \& 1] = \max(f[v \& 1], f[v \& 1 \oplus 1] - x) + v$ 。

答案为 $f[0]$ 和 $f[1]$ 中的较大值。

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

1

2

3

4

5

6

7

8

class Solution:
    def maxScore(self, nums: List[int], x: int) -> int:
        f = [-inf] * 2
        f[nums[0] & 1] = nums[0]
        for v in nums[1:]:
            f[v & 1] = max(f[v & 1], f[v & 1 ^ 1] - x) + v
        return max(f)

speed

复杂度分析

指标	值
时间	complexity depends on the DP implementation. A naive approach is O(n^2) by checking all previous indices. Space complexity is O(n) to store the DP array. Optimizations using monotonic queues or parity tracking can reduce redundant calculations.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Are you tracking maximum scores separately for even and odd parity transitions?
question_mark
Can you optimize DP transitions to avoid O(n^2) iteration over all previous indices?
question_mark
How do you handle penalties when moving between numbers of different parity?

warning

常见陷阱

外企场景

error
Forgetting to subtract x for parity changes between consecutive positions.
error
Assuming all moves contribute positively without checking parity penalties.
error
Overlooking the need to track separate maximum scores for even and odd parity states.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Penalty depends on the difference between numbers instead of fixed x.
arrow_right_alt
Allow only moves to adjacent positions rather than any index ahead.
arrow_right_alt
Maximize score with multiple penalty types for different transitions.

help

常见问题

外企场景

继续练习

#2771 构造最长非递减子数组 #2770 达到末尾下标所需的最大跳跃次数 #2809 使数组和小于等于 x 的最少时间