Visit Array Positions to Maximize Score — Problem & Solution
Visit Array Positions to Maximize Score solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Visit Array Positions to Maximize Score is a medium coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You start at index 0 of nums with a score of nums[0]. From index i you may move to any index j > i; arriving at j adds nums[j] to the score. If nums[i] and nums[j] have different parities (one even, one odd), the move also costs x points.
You may stop at any time. Return the maximum score you can finish with.
CodeKairo bound: nums[i] <= 10^4 (LeetCode allows 10^6) so that the answer fits in a 32-bit integer.
Example 1
Input: nums = [2,3,6,1,9,2], x = 5
Output: 13
Explanation: Visit 0 → 2 → 3 → 4: 2 + 6 + 1 + 9 − 5 (the move 6 → 1 changes parity).
Example 2
Input: nums = [2,4,6,8], x = 3
Output: 20
Explanation: All even: take everything.
Example 3
Input: nums = [7,10,9], x = 2
Output: 22
Constraints
2 <= nums.length <= 10^51 <= nums[i] <= 10^41 <= x <= 10^6
Hints for Visit Array Positions to Maximize Score
Hint 1
The penalty depends only on the parity of the last value visited, not on its position.
Hint 2
Keep two numbers: the best score of a path ending on an even value and on an odd value.
Hint 3
For
nums[j]with parityp:best[p] = max(best[p], max(best[p], best[1-p] - x) + nums[j]).
How to solve Visit Array Positions to Maximize Score
A path's future depends only on the parity of where it currently stands. So among all paths ending before j, only the best ending on an even value and the best ending on an odd value matter.
Approach
best[p] = -∞for both parities, thenbest[nums[0] % 2] = nums[0].- For each later
v = nums[j]with parityp:cand = max(best[p] + v, best[1-p] + v - x); setbest[p] = max(best[p], cand). - Return
max(best[0], best[1]).
Why it works
Any path ending at j arrives from some earlier index i; its score is that path's score plus nums[j], minus x exactly when the parities differ. The best such predecessor among same-parity indices is best[p] and among opposite-parity ones is best[1-p], so cand is the optimum ending at j. Keeping best[p] as a running maximum also allows skipping j.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- The start index 0 is mandatory — the opposite parity starts at -∞, not 0.
- Skipping elements is allowed, so
best[p]must never decrease. - With the original bounds the score needs 64 bits; with these it stays below 2^31.
Reference solution
Python
from typing import List
def maxScore(nums: List[int], x: int) -> int:
NEG = -10**18
best = [NEG, NEG]
best[nums[0] % 2] = nums[0]
for v in nums[1:]:
p = v % 2
cand = max(best[p] + v, best[1 - p] + v - x)
if cand > best[p]:
best[p] = cand
return max(best)Java
public static int maxScore(int[] nums, int x) {
final long NEG = Long.MIN_VALUE / 4;
long[] best = {NEG, NEG};
best[nums[0] % 2] = nums[0];
for (int j = 1; j < nums.length; j++) {
int v = nums[j], p = v % 2;
long cand = Math.max(best[p] + v, best[1 - p] + v - x);
if (cand > best[p]) best[p] = cand;
}
return (int) Math.max(best[0], best[1]);
}C++
int maxScore(vector<int>& nums, int x) {
const long long NEG = LLONG_MIN / 4;
long long best[2] = {NEG, NEG};
best[nums[0] % 2] = nums[0];
for (size_t j = 1; j < nums.size(); j++) {
int v = nums[j], p = v % 2;
long long cand = max(best[p] + v, best[1 - p] + v - x);
if (cand > best[p]) best[p] = cand;
}
return (int) max(best[0], best[1]);
}JavaScript
var maxScore = function(nums, x) {
var best = [-Infinity, -Infinity];
best[nums[0] % 2] = nums[0];
for (var j = 1; j < nums.length; j++) {
var v = nums[j], p = v % 2;
var cand = Math.max(best[p] + v, best[1 - p] + v - x);
if (cand > best[p]) best[p] = cand;
}
return Math.max(best[0], best[1]);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming