Visit Array Positions to Maximize Score

Medium
1497.

Visit Array Positions to Maximize Score

Visit Array Positions to Maximize Score is a medium coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.

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^5
  • 1 <= nums[i] <= 10^4
  • 1 <= x <= 10^6
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} x
 * @return {number}
 */
var maxScore = function(nums, x) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^5
  • 1 <= nums[i] <= 10^4
  • 1 <= x <= 10^6

Hints for Visit Array Positions to Maximize Score

  1. Hint 1

    The penalty depends only on the parity of the last value visited, not on its position.

  2. Hint 2

    Keep two numbers: the best score of a path ending on an even value and on an odd value.

  3. Hint 3

    For nums[j] with parity p: 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

  1. best[p] = -∞ for both parities, then best[nums[0] % 2] = nums[0].
  2. For each later v = nums[j] with parity p: cand = max(best[p] + v, best[1-p] + v - x); set best[p] = max(best[p], cand).
  3. 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