LeetCode 2786 - Visit Array Positions to Maximize Score

The problem presents a 0-indexed array nums of integers and a positive integer x. You start at the first element, nums[0], and can move to any subsequent position j where j i. For each element you visit, you accumulate its value as part of your score.

leetcodemediumarraydynamic-programming

LeetCode Problem 2786

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem presents a 0-indexed array nums of integers and a positive integer x. You start at the first element, nums[0], and can move to any subsequent position j where j > i. For each element you visit, you accumulate its value as part of your score. However, if the number at your current position and the number at the next position have different parities (one is odd, the other is even), you incur a penalty of x. The goal is to determine the maximum possible total score you can achieve following these movement rules.

The input array can be large (2 <= nums.length <= 10^5), and element values and x can go up to 10^6. This implies that a brute-force solution examining all sequences of positions is infeasible. Instead, we must find an efficient approach that accounts for parity transitions and accumulates the maximum score efficiently.

Important edge cases include arrays where all elements are even or odd, arrays with alternating parity, and large penalty values where avoiding parity changes may be optimal.

Approaches

Brute Force Approach

A naive approach is to recursively explore every valid sequence of positions starting from index 0. For each move from i to j, you calculate the score of nums[j] and subtract x if the parity differs. You maintain the maximum score across all paths. This method works because it considers every possible sequence and applies the penalty exactly as described.

The problem with brute force is its exponential complexity. With an array of length n, there are 2^(n-1) potential paths (each element can be included or skipped), which is completely infeasible for n up to 10^5.

Optimal Approach

The key insight is to track the maximum score achievable ending with an even number and ending with an odd number as we iterate through the array. We only need two values: max_even and max_odd. For each nums[i], the maximum score if we end at i is either adding it to the best sequence of the same parity (no penalty) or to the best sequence of opposite parity minus x (penalty). This reduces the problem to linear time and constant space.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Explore all sequences recursively
Optimal O(n) O(1) Track only max_even and max_odd, update iteratively

Algorithm Walkthrough

  1. Initialize two variables, max_even and max_odd. If nums[0] is even, set max_even = nums[0] and max_odd = -inf. Otherwise, set max_odd = nums[0] and max_even = -inf.
  2. Iterate through the array starting from index 1.
  3. For each number nums[i], check its parity.
  4. If it is even, calculate the potential score by either adding it to max_even (no penalty) or max_odd - x (penalty for switching parity). Update max_even to the maximum of these two values.
  5. If it is odd, calculate the potential score by either adding it to max_odd (no penalty) or max_even - x (penalty for switching parity). Update max_odd to the maximum of these two values.
  6. Continue this process until the end of the array.
  7. The result is the maximum of max_even and max_odd, which represents the best achievable score regardless of ending parity.

Why it works: This approach works because we only need to consider the best sequence ending with each parity at each step. Any longer sequence ending at i with the same parity can be built by extending the optimal sequence of the previous parity, ensuring that no optimal path is missed.

Python Solution

from typing import List

class Solution:
    def maxScore(self, nums: List[int], x: int) -> int:
        max_even = float('-inf')
        max_odd = float('-inf')
        
        if nums[0] % 2 == 0:
            max_even = nums[0]
        else:
            max_odd = nums[0]
        
        for num in nums[1:]:
            if num % 2 == 0:
                max_even = max(max_even + num, max_odd - x + num)
            else:
                max_odd = max(max_odd + num, max_even - x + num)
        
        return max(max_even, max_odd)

The implementation begins by initializing max_even and max_odd based on the parity of the first element. We then iterate through the array, updating the maximum scores for even and odd endings by considering both extending the same parity or switching parity (and subtracting x). The final answer is the maximum of the two.

Go Solution

func maxScore(nums []int, x int) int64 {
    var maxEven, maxOdd int64
    maxEven, maxOdd = -1<<60, -1<<60
    
    if nums[0]%2 == 0 {
        maxEven = int64(nums[0])
    } else {
        maxOdd = int64(nums[0])
    }
    
    for i := 1; i < len(nums); i++ {
        num := int64(nums[i])
        if num%2 == 0 {
            newEven := max(maxEven + num, maxOdd - int64(x) + num)
            maxEven = newEven
        } else {
            newOdd := max(maxOdd + num, maxEven - int64(x) + num)
            maxOdd = newOdd
        }
    }
    
    return max(maxEven, maxOdd)
}

func max(a, b int64) int64 {
    if a > b {
        return a
    }
    return b
}

In Go, we handle potential integer overflows by using int64. The logic mirrors the Python version, using a helper max function to simplify comparisons.

Worked Examples

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

i num max_even max_odd Explanation
0 2 2 -inf Initialize
1 3 2 max(3 + -inf, 2 - 5 + 3) = 0 Switching parity incurs penalty
2 6 max(2 + 6, 0 - 5 + 6) = 8 0 Extend even or switch from odd
3 1 8 max(0 + 1, 8 - 5 + 1) = 4 Extend odd or switch from even
4 9 8 max(4 + 9, 8 - 5 + 9) = 12 Choose best
5 2 max(8 + 2, 12 - 5 + 2) = 12 Extend even or switch

Final result: max(12,12) = 12

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

i num max_even max_odd
0 2 2 -inf
1 4 max(2+4, -inf-3+4) = 6 -inf
2 6 max(6+6, -inf-3+6) = 12 -inf
3 8 max(12+8, -inf-3+8) = 20 -inf

Final result: 20

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass through the array, constant work per element
Space O(1) Only two variables tracked, no additional data structures

The algorithm scales linearly with input size and uses minimal extra memory, suitable for large arrays.

Test Cases

# Provided examples
assert Solution().maxScore([2,3,6,1,9,2], 5) == 13  # mix of parities
assert Solution().maxScore([2,4,6,8], 3) == 20      # all same parity

# Boundary values
assert Solution().maxScore([1,1], 1) == 2          # smallest array, both odd
assert Solution().maxScore([2,1], 10) == 2         # penalty larger than gain, skip switch

# Alternating parity
assert Solution().maxScore([1,2,1,2,1], 1) == 3    # optimal to sometimes skip

# Large values
assert Solution().maxScore([10**6]*10**5, 1) == 10**6 * 10**5  # all same parity, no penalty
Test Why
[2,3,6,1,9,2], x=5 Tests switching parity and penalty calculation
[2,4,6,8], x=3 Tests all elements same parity, no