We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Visit Array Positions to Maximize Score

Number: 2893

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

You are given a 0-indexed integer array nums and a positive integer x. You start at position 0 (gaining nums[0] points), and you can move to any position j > i. For every move, you add nums[j] to your score. Additionally, if nums[i] and nums[j] have different parities, you lose x points. The goal is to choose a sequence of moves (possibly skipping some positions) so that the total score is maximized.

Key Insights

  • The decision at each position depends only on the parity of the current number and the best score you can have ending in an even or odd number.
  • Use dynamic programming with two variables: bestEven (maximum score when last visited number is even) and bestOdd (maximum score when last visited number is odd).
  • When considering a new number, there are two cases:
    • If the number has the same parity as the last visited number, simply add the value.
    • If the parity differs, add the value but subtract x.
  • It is not necessary to choose every position; update the best scores as you iterate to account for potential skips.

Space and Time Complexity

Time Complexity: O(n) because we iterate through the array only once. Space Complexity: O(1) since we only maintain two state variables.

Solution

We use a dynamic programming approach by maintaining two variables: bestEven and bestOdd. They store the maximum score possible so far ending with an even or odd number, respectively. Initialize these based on the parity of nums[0]. For each subsequent element in nums, update the corresponding state by considering whether transitioning from the same or the opposite parity is more beneficial (taking into account the penalty x when parities differ). Finally, the answer will be the maximum of the two states. This greedy DP strategy ensures that we always pick the optimal score up to the current index.

Code Solutions

# Python solution with detailed comments

def maxScore(nums, x):
    # Initialize the DP variables based on the parity of the first element
    # bestEven: maximum score ending in an even number
    # bestOdd: maximum score ending in an odd number
    if nums[0] % 2 == 0:
        bestEven = nums[0]
        bestOdd = float('-inf')
    else:
        bestOdd = nums[0]
        bestEven = float('-inf')
    
    # Iterate over the rest of the elements in the array
    for val in nums[1:]:
        if val % 2 == 0:
            # If current value is even, consider two transitions:
            # 1) Coming from bestEven: same parity so add value
            # 2) Coming from bestOdd: different parity so add value and subtract penalty x
            newEven = max(bestEven + val, bestOdd + val - x)
            # Since current value is even, bestOdd remains unchanged
            bestEven = max(bestEven, newEven)
        else:
            # If current value is odd, consider two transitions:
            # 1) Coming from bestOdd: same parity so add value
            # 2) Coming from bestEven: different parity so add value and subtract x
            newOdd = max(bestOdd + val, bestEven + val - x)
            bestOdd = max(bestOdd, newOdd)
    
    # Return the maximum score possible overall
    return max(bestEven, bestOdd)

# Example usage:
print(maxScore([2,3,6,1,9,2], 5))  # Expected output: 13
← Back to All Questions