Skip to main content
Talentd

Visit Array Positions to Maximize Score - Solution & Explanation

MediumArrayDynamic Programming24 min read
Practice this problem

Problem Statement

You are given a 0-indexed integer array nums and a positive integer x.

You are initially at position 0 in the array and you can visit other positions according to the following rules:

  • If you are currently in position i, then you can move to any position j such that i < j.
  • For each position i that you visit, you get a score of nums[i].
  • If you move from a position i to a position j and the parities of nums[i] and nums[j] differ, then you lose a score of x.

Return the maximum total score you can get.

Note that initially you have nums[0] points.

 

Example 1:

Input: nums = [2,3,6,1,9,2], x = 5
Output: 13
Explanation: 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
Explanation: 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

Approach Overview

Problem Overview: You start at index 0 and can move to any later index in the array. Each visited value adds to your score, but switching between even and odd numbers subtracts a penalty x. The goal is to choose positions that maximize the total score.

Approach 1: Greedy with Memoization (Top-Down DP) (O(n) time, O(n) space)

This approach models the problem as a recursive decision process. From each index, you decide which future position to visit next while tracking the parity of the last selected number. Memoization stores the best score achievable from a given index and parity state to avoid recomputation. The key observation is that the only information affecting future choices is the current index and whether the previous value was even or odd. This reduces the state space and makes the recursion efficient. This technique combines greedy selection with dynamic programming caching.

Approach 2: Dynamic Programming with Parity States (O(n) time, O(1) space)

The optimal solution keeps track of the best score achievable when the last chosen number is even and when it is odd. Maintain two variables: bestEven and bestOdd. While iterating through the array, compute the best possible score if the current number is selected. If the parity matches the previous state, simply add the value; if it differs, subtract the penalty x. Update the corresponding parity state with the maximum possible score. Because each element is processed once and only two states are maintained, the algorithm runs in linear time and constant space.

This solution works because the penalty only depends on parity changes, not on the exact index previously chosen. That allows the problem to collapse into two running states instead of tracking all previous indices. The pattern appears frequently in array optimization problems where transitions depend on limited state.

Recommended for interviews: The dynamic programming parity-state solution is what interviewers typically expect. It demonstrates the ability to compress DP state and recognize that only parity matters, reducing a potential O(n²) search to O(n). Mentioning the memoized recursive version first can show your reasoning process, but implementing the O(n) DP with two variables proves strong optimization skills.

Approach 1: Dynamic Programming Approach

The Dynamic Programming approach leverages an array dp where each element dp[i] signifies the maximum score obtainable by the time we reach the i-th index in nums. The logic involves iterating through each element and calculating the potential score by transitioning from previously visited elements to the current one, accounting for the parity penalty when applicable.

We initialize dp[0] with nums[0], as this is the starting point. For each subsequent index j, traverse all prior indices i and update dp[j] with either the current point at index j itself, or the maximum score possible by transitioning from dp[i] and adjusting for penalties where necessary. This results in O(n^2) time complexity, necessitating optimization.

This C code initializes a dynamic programming table dp where dp[i] implies the max score obtainable by reaching nums[i]. We initialize dp[0] with nums[0] since it's our starting point. The nested loop iterates through subsequent indexes and evaluates if moving from a prior position results in a higher score, adjusting for any parity penalties. The outer loop determines the max score overall after possible routes are computed. The final maximum score across all potentials in dp is returned.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity for this approach is O(n^2) due to the double loop structure traversing each point for potential max till accumulation. Memory complexity is O(n) as a single auxiliary array dp stores results across indices.

Try this approach in the editor →

Approach 2: Greedy Approach with Memoization

The greedy approach, combined with memoization, aims to reduce computational time by strategically choosing the best potential next index to maximize score with minimum loss. The memoization stores results of previously computed indices, preventing re-evaluation, and improving efficiency over traditional DP.

This approach initializes a recursive function that checks transitions with penalties, caching results for overlap avoidance. It enables a selective path based on higher weightage preference calculated through indirect cached evaluations of consequences of choices, ensuring potential gain maximization in score vigilance.

This C solution employs a recursive function maxScoreRecursive using memoization to cache already computed best scores for positions, retrieving further calculation if re-check attempts at any processed indices arises. Recursions simulations enact subset score accumulation leveraging parity penalty checks for optimal path aggregations.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Considering overhead removal through memoized patterns manipulation, effective time complexity is O(n^2) helped slightly by minimized recomputation. Space needs relay primary through size-determined auxiliary storage sizing dimensionally in O(n).

Try this approach in the editor →

Approach 3: Dynamic Programming

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

  1. Moving from position i to position j, if nums[i] and nums[j] have different parities, then x points will be lost;
  2. Moving from position i to position j, if nums[i] and nums[j] have the same parity, then no points will be lost.

Therefore, we can use an array f of length 2 to represent the maximum score when the current position's parity is 0 and 1. Initially, the values of f are -infty, and then we initialize f[nums[0] \& 1] = nums[0], indicating the score at the initial position.

Next, we start traversing the array nums from position 1. For each position i corresponding to the value v, we update the value of f[v \& 1] to be the larger value between f[v \& 1] and f[v \& 1 \oplus 1] - x plus v, i.e., f[v \& 1] = max(f[v \& 1], f[v \& 1 \oplus 1] - x) + v.

The answer is the larger value between f[0] and f[1].

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

The time complexity for this approach is O(n^2) due to the double loop structure traversing each point for potential max till accumulation. Memory complexity is O(n) as a single auxiliary array dp stores results across indices.

Greedy Approach with Memoization

Considering overhead removal through memoized patterns manipulation, effective time complexity is O(n^2) helped slightly by minimized recomputation. Space needs relay primary through size-determined auxiliary storage sizing dimensionally in O(n).

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy with Memoization (Top-Down DP)O(n)O(n)Useful for understanding the decision process and demonstrating recursion with memoization.
Dynamic Programming with Parity StatesO(n)O(1)Best practical solution. Efficient for large arrays and typically expected in coding interviews.

Video Solution

Leetcode BiWeekly contest 109 - Medium - Visit Array Positions to Maximize Score • Prakhar Agrawal • 1,531 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Visit Array Positions to Maximize Score easy or hard?
The problem is rated Medium on LeetCode. The challenge is recognizing that only parity affects the penalty, allowing the dynamic programming state to be reduced to two variables instead of tracking every previous index.
How to solve Visit Array Positions to Maximize Score in O(n)?
Maintain two running scores: bestEven and bestOdd. When visiting a new number, compute the score by either continuing with the same parity or switching parity and subtracting x. Update the corresponding state with the maximum value. A single pass through the array yields the optimal result.
What is the best approach for Visit Array Positions to Maximize Score?
The optimal approach uses dynamic programming with two parity states. Track the best score when the last selected number is even and when it is odd. While iterating through the array, update these states and subtract the penalty x when parity changes. This achieves O(n) time and O(1) space complexity.
What data structure is used in Visit Array Positions to Maximize Score?
The solution mainly relies on array traversal combined with dynamic programming state tracking. Instead of storing a full DP table, two variables track the best score for even and odd parity states.
What is the time complexity of Visit Array Positions to Maximize Score?
The optimal dynamic programming solution runs in O(n) time because each element is processed exactly once. Only two state variables are maintained for even and odd parity scores, giving O(1) space complexity.
Visit Array Positions to Maximize Score Python or Java solution approach?
Both Python and Java implementations typically use the same DP strategy with two variables. Iterate through the array, update bestEven or bestOdd depending on the current number’s parity, and subtract x when switching parity. This keeps the solution O(n) with constant space.
Is Visit Array Positions to Maximize Score asked at Google, Amazon, or Meta?
This problem represents a common interview pattern involving dynamic programming state compression and parity-based transitions. Variations of this pattern frequently appear in interviews at companies like Amazon, Google, and Meta when testing optimization over arrays.

Ready to solve this problem?

Practice Visit Array Positions to Maximize Score with our built-in code editor and test cases.

Practice on FleetCode
Previous

Jump Game II

Next

Stone Game