Watch 10 video solutions for Visit Array Positions to Maximize Score, a medium level problem involving Array, Dynamic Programming. This walkthrough by Prakhar Agrawal has 1,511 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
i, then you can move to any position j such that i < j.i that you visit, you get a score of nums[i].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 <= 1051 <= nums[i], x <= 106Problem 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 | Time | Space | When 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 States | O(n) | O(1) | Best practical solution. Efficient for large arrays and typically expected in coding interviews. |