Scale Engineer

Visit Array Positions to Maximize Score

Med
#2498Time: O(n^2), where n is the number of elements in `nums`. There are two nested loops: the outer loop runs `n-1` times, and the inner loop runs up to `n-1` times for each outer iteration.Space: O(n), where n is the number of elements in `nums`. This is required for the DP array.
Patterns
Dynamic Programming
Data structures
Array

Prompt

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 position j such that i < j.
  • For each position i that you visit, you get a score of nums[i].
  • If you move from a position 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 <= 105
  • 1 <= nums[i], x <= 106

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses a straightforward dynamic programming solution. We define dp[i] as the maximum score achievable by ending a path of visited positions at index i. To compute dp[i], we consider all possible preceding positions j (where j < i) that we could have jumped from. The score for jumping from j to i is the score of the path ending at j (dp[j]) plus the value nums[i], minus a penalty x if the parities of nums[j] and nums[i] differ. We take the maximum over all possible j's to determine dp[i]. The final answer is the maximum score found in the entire dp array.

Algorithm

  • Initialize a long array dp of size n, where n is the length of nums. dp[i] will store the maximum score of a path ending at index i.
  • Set the base case: dp[0] = nums[0], as any path must start at index 0.
  • Iterate with a variable i from 1 to n-1:
    • For each i, iterate with a variable j from 0 to i-1.
    • Calculate the score if we jump from a path ending at j to the element at i.
    • The score is dp[j] + nums[i]. A penalty x is subtracted if nums[i] and nums[j] have different parities.
    • Update dp[i] with the maximum score found among all possible previous positions j.
    • The recurrence relation is: dp[i] = max(dp[i], dp[j] + nums[i] - penalty).
  • After filling the dp array, the answer is the maximum value within dp, since the path can end at any index.

Walkthrough

We create a DP array, dp, of the same size as nums. dp[i] will store the maximum score of a path ending at index i.

The base case is dp[0] = nums[0], as the path must start at index 0. We initialize all other dp entries to a very small number.

We then iterate from i = 1 to n-1. For each i, we need to find the best previous position j to jump from. We do this by iterating j from 0 to i-1. For each j, we calculate the potential score if we extend the path ending at j by visiting i. This score is dp[j] + nums[i]. If nums[j] and nums[i] have different parities, we subtract the penalty x.

The value of dp[i] is then the maximum of these potential scores over all j < i. The recurrence relation can be expressed as: dp[i] = max_{0 <= j < i} (dp[j] + nums[i] - ((nums[j] % 2 != nums[i] % 2) ? x : 0))

After the loops complete, the dp array is filled. The maximum score might be achieved by ending at any index, so the final answer is the maximum value in the dp array.

class Solution {    public long maxScore(int[] nums, int x) {        int n = nums.length;        long[] dp = new long[n];                dp[0] = nums[0];         for (int i = 1; i < n; i++) {            long maxPrevJumpScore = Long.MIN_VALUE;            for (int j = 0; j < i; j++) {                long penalty = (nums[i] % 2 != nums[j] % 2) ? x : 0;                maxPrevJumpScore = Math.max(maxPrevJumpScore, dp[j] - penalty);            }            dp[i] = nums[i] + maxPrevJumpScore;        }         long maxTotalScore = Long.MIN_VALUE;        for (long score : dp) {            maxTotalScore = Math.max(maxTotalScore, score);        }        return maxTotalScore;    }}

Complexity

Time

O(n^2), where n is the number of elements in `nums`. There are two nested loops: the outer loop runs `n-1` times, and the inner loop runs up to `n-1` times for each outer iteration.

Space

O(n), where n is the number of elements in `nums`. This is required for the DP array.

Trade-offs

Pros

  • The logic is a direct translation of the problem statement into a DP recurrence, making it relatively easy to understand.

  • It correctly solves the problem for smaller input sizes.

Cons

  • The time complexity of O(n^2) is too slow for the given constraints (n <= 10^5) and will result in a 'Time Limit Exceeded' error on most platforms.

  • Uses O(n) space, which might be significant for very large n.

Solutions

class Solution {public  long maxScore(int[] nums, int x) {    long[] f = new long[2];    Arrays.fill(f, -(1L << 60));    f[nums[0] & 1] = nums[0];    for (int i = 1; i < nums.length; ++i) {      f[nums[i] & 1] =          Math.max(f[nums[i] & 1] + nums[i], f[nums[i] & 1 ^ 1] + nums[i] - x);    }    return Math.max(f[0], f[1]);  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem