#2786

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Visit Array Positions to Maximize Score

Maximize your score by visiting positions in an array while handling penalties for parity changes efficiently with DP.

Problem Statement

You are given a 0-indexed integer array nums and a positive integer x. You start at position 0 and can move to subsequent positions to accumulate scores. If you move between numbers of different parity, a penalty of x is subtracted from your total score.

Return the maximum total score achievable by visiting positions in the array following these rules. Each move can go to any index ahead, and the goal is to plan a sequence that maximizes the sum of visited numbers minus penalties for parity changes.

Examples

Example 1

Input: nums = [2,3,6,1,9,2], x = 5

Output: 13

We can visit the following positions in the array: 0 -> 2 -> 3 -> 4. The corresponding values are 2, 6, 1 and 9. Since the integers 6 and 1 have different parities, the move 2 -> 3 will make you lose a score of x = 5. The total score will be: 2 + 6 + 1 + 9 - 5 = 13.

Example 2

Input: nums = [2,4,6,8], x = 3

Output: 20

All the integers in the array have the same parities, so we can visit all of them without losing any score. The total score is: 2 + 4 + 6 + 8 = 20.

Constraints

2 <= nums.length <= 105
1 <= nums[i], x <= 106

Solution Approach

Define DP State

Let dp[i] represent the maximum score attainable when reaching index i. Initialize dp[0] with nums[0]. This ensures each state captures the best score ending at each position while accounting for parity penalties.

State Transitions

For each index i, consider all previous indices j < i. Update dp[i] as dp[j] + nums[i] - (x if nums[i] and nums[j] have different parity else 0). This directly implements the state transition dynamic programming pattern.

Iterate and Return

After filling the dp array, return the maximum value in dp. This approach ensures all paths and parity penalties are considered, capturing the maximum achievable score.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time 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.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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].

terminal

Solution

Solution 1: Dynamic Programming

Based on the problem description, we can draw the following conclusions:

1

2

3

4

5

6

7

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)

Continue Practicing

#2771 longest non decreasing subarray from two arrays #2770 maximum number of jumps to reach the last index #2809 minimum time to make array sum at most x