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.
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.
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.
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.
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).
Based on the problem description, we can draw the following conclusions:
i to position j, if nums[i] and nums[j] have different parities, then x points will be lost;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).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| 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 |
| 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 | — |
| 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. |
Leetcode BiWeekly contest 109 - Medium - Visit Array Positions to Maximize Score • Prakhar Agrawal • 1,511 views views
Watch 9 more video solutions →Practice Visit Array Positions to Maximize Score with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor