Visit Array Positions to Maximize Score - Video Solutions
Leetcode BiWeekly contest 109 - Medium - Visit Array Positions to Maximize Score
Visit Array Positions to Maximize Score - Video Solution
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,531 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 positionjsuch thati < j. - For each position
ithat you visit, you get a score ofnums[i]. - If you move from a position
ito a positionjand the parities ofnums[i]andnums[j]differ, then you lose a score ofx.
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 <= 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.
Complexity Analysis
| 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. |