Problem Description

You start at position 0 in a 0-indexed integer array nums and can jump forward to collect scores. Here are the rules:

1. Movement: From any position i, you can jump to any position j where j > i (you can only move forward).

2. Scoring: When you visit position i, you gain nums[i] points.

3. Parity Penalty: If you jump from position i to position j and nums[i] and nums[j] have different parities (one is odd and the other is even), you lose x points.

4. Starting Score: You automatically start with nums[0] points since you begin at position 0.

Your goal is to find the maximum total score possible by choosing an optimal path through the array.

For example, if nums = [2, 3, 6, 1, 9, 2] and x = 5:

• You start at position 0 with score 2 (even)
• If you jump to position 1 (value 3, odd), you lose 5 points for the parity change
• If you jump to position 2 (value 6, even), no penalty since both are even
• You continue choosing jumps to maximize your total score

The solution uses dynamic programming to track the maximum score achievable when the last visited number had even parity (f[0]) or odd parity (f[1]). For each new position, it calculates the best score by either continuing with the same parity (no penalty) or switching parity (subtracting x).

Intuition

The key insight is that the penalty x only depends on whether we're switching between even and odd numbers, not on the specific positions or values. This means at any point in our journey, what really matters is:

1. Our current total score
2. Whether the last number we visited was even or odd

Think of it this way: when we're at position i, we need to decide where to jump next. The cost of jumping depends only on the parity of our current number and the parity of where we're jumping to. If we jump to a number with the same parity, it's free. If we switch parity, we pay x.

This naturally leads to tracking two states as we progress through the array:

• The maximum score if our last visited number was even
• The maximum score if our last visited number was odd

Why does this work? Because when we reach any position j, we can arrive there from:

• Any previous even number (if nums[j] is even, no penalty; if nums[j] is odd, pay x)
• Any previous odd number (if nums[j] is odd, no penalty; if nums[j] is even, pay x)

Since we want the maximum score, we only need to remember the best score for "last visited was even" and "last visited was odd". We don't need to track every possible path or position - just these two optimal states.

As we process each number in the array, we update the appropriate state (even or odd) by choosing the better option: either continuing from the same parity (adding the current value) or switching from the opposite parity (adding the current value but subtracting x).

This reduces what could be a complex path-finding problem to simply maintaining two values throughout our traversal: f[0] for the best score ending on an even number, and f[1] for the best score ending on an odd number.

Learn more about Dynamic Programming patterns.

Solution Approach

We implement the solution using dynamic programming with state compression. The algorithm uses an array f of length 2 to track the maximum scores:

• f[0]: Maximum score when the last visited number was even
• f[1]: Maximum score when the last visited number was odd

Initialization:

f = [-inf] * 2
f[nums[0] & 1] = nums[0]

We initialize both states to negative infinity to represent unvisited states. Then we set the starting position: f[nums[0] & 1] = nums[0]. The expression nums[0] & 1 gives us 0 if nums[0] is even, 1 if odd. This sets our initial score based on the parity of the first element.

State Transition: For each subsequent number v in the array (starting from index 1):

f[v & 1] = max(f[v & 1], f[v & 1 ^ 1] - x) + v

Let's break down this transition formula:

• v & 1: Determines the parity of the current number (0 for even, 1 for odd)
• f[v & 1]: The current best score for ending on this parity
• f[v & 1 ^ 1]: The best score for ending on the opposite parity (XOR with 1 flips between 0 and 1)

The transition considers two possibilities:

1. Same parity transition: Jump from a previous position with the same parity to current position. Cost = f[v & 1] + v (no penalty)
2. Different parity transition: Jump from a previous position with opposite parity. Cost = f[v & 1 ^ 1] - x + v (subtract penalty x)

We take the maximum of these two options. This ensures we're always maintaining the best possible score for reaching a number of each parity.

Final Answer:

return max(f)

After processing all numbers, we return the maximum between f[0] and f[1], which represents the best score achievable regardless of the parity of the last visited number.

The beauty of this approach is its efficiency: we only need O(1) space (just two values) and O(n) time to process the array once. The algorithm correctly handles all forward jumps implicitly because we update states sequentially - when we process position j, all positions i < j have already updated the f array with their best scores.

Example Walkthrough

Let's trace through a small example: nums = [2, 3, 6, 1, 9, 2] and x = 5.

We'll track two values throughout:

• f[0]: best score ending on an even number
• f[1]: best score ending on an odd number

Initial Setup:

• Start at position 0 with value 2 (even)
• f[0] = 2 (we collected 2 points and it's even)
• f[1] = -inf (haven't visited any odd number yet)

Position 1: value = 3 (odd)

• Current f[1] = -inf
• From even to odd: f[0] - x + 3 = 2 - 5 + 3 = 0
• New f[1] = max(-inf, 0) + 3 = 3
• State: f[0] = 2, f[1] = 3

Position 2: value = 6 (even)

• Current f[0] = 2
• From odd to even: f[1] - x + 6 = 3 - 5 + 6 = 4
• From even to even: f[0] + 6 = 2 + 6 = 8
• New f[0] = max(8, 4) = 8
• State: f[0] = 8, f[1] = 3

Position 3: value = 1 (odd)

• Current f[1] = 3
• From even to odd: f[0] - x + 1 = 8 - 5 + 1 = 4
• From odd to odd: f[1] + 1 = 3 + 1 = 4
• New f[1] = max(4, 4) = 4
• State: f[0] = 8, f[1] = 4

Position 4: value = 9 (odd)

• Current f[1] = 4
• From even to odd: f[0] - x + 9 = 8 - 5 + 9 = 12
• From odd to odd: f[1] + 9 = 4 + 9 = 13
• New f[1] = max(13, 12) = 13
• State: f[0] = 8, f[1] = 13

Position 5: value = 2 (even)

• Current f[0] = 8
• From odd to even: f[1] - x + 2 = 13 - 5 + 2 = 10
• From even to even: f[0] + 2 = 8 + 2 = 10
• New f[0] = max(10, 10) = 10
• State: f[0] = 10, f[1] = 13

Final Answer: max(f[0], f[1]) = max(10, 13) = 13

The optimal path that achieves score 13 is: position 0 (score 2) → position 2 (score 2 + 6 = 8) → position 4 (score 8 - 5 + 9 = 12, paying penalty for even→odd) → stay at position 4 (final score 13). Note that we could also go 0→1→4 for the same score.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. The algorithm iterates through the array once starting from index 1, performing constant-time operations for each element (bitwise AND operation v & 1, XOR operation v & 1 ^ 1, max comparison, and addition).

The space complexity is O(1). The algorithm uses a fixed-size array f of length 2 to track the maximum scores for odd and even numbers, which requires constant extra space regardless of the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Forgetting to Initialize Unvisited States to Negative Infinity

The Problem: A common mistake is initializing the DP array with zeros instead of negative infinity:

# WRONG
dp = [0] * 2
dp[nums[0] & 1] = nums[0]

This causes incorrect results because 0 is a valid score that suggests we've visited a position with that parity, when in reality we haven't. This leads to invalid transitions where we might "jump" from a state we never actually reached.

Why This Fails: Consider nums = [10, 5, 3] with x = 15:

• With wrong initialization: dp = [0, 0], then dp[0] = 10 → dp = [10, 0]
• Processing 5 (odd): dp[1] = max(0, 10-15) + 5 = 5 (incorrectly uses the unvisited dp[1]=0)
• This gives a wrong path that never actually existed

The Solution: Always initialize unvisited states with negative infinity:

dp = [float('-inf')] * 2
dp[nums[0] & 1] = nums[0]

This ensures we only make transitions from states we've actually visited.

Pitfall 2: Incorrect Parity Calculation

The Problem: Using modulo operator instead of bitwise AND for parity:

# WRONG - Can be problematic with negative numbers
current_parity = num % 2

Why This Fails: In Python, (-3) % 2 returns 1, but we want to check if the absolute value is odd. While this specific problem likely has non-negative values, using bitwise operations is both safer and more efficient.

The Solution: Always use bitwise AND for parity checking:

current_parity = num & 1  # Works correctly for all integers

Pitfall 3: Overwriting State Before Using It

The Problem: Some might try to update both states in a loop, accidentally using an already-updated value:

# WRONG
for num in nums[1:]:
    if num & 1:  # odd
        dp[1] = max(dp[1], dp[0] - x) + num
        dp[0] = dp[1] - x  # WRONG: uses the just-updated dp[1]
    else:  # even
        dp[0] = max(dp[0], dp[1] - x) + num
        dp[1] = dp[0] - x  # WRONG: uses the just-updated dp[0]

Why This Fails: Once we update a state, we lose the previous value needed for other calculations in the same iteration.

The Solution: Only update the state corresponding to the current number's parity:

for num in nums[1:]:
    current_parity = num & 1
    opposite_parity = current_parity ^ 1
    dp[current_parity] = max(
        dp[current_parity],
        dp[opposite_parity] - x
    ) + num

This ensures we only update one state per iteration, preserving the other state's value for future transitions.