Skip to content

3221. Maximum Array Hopping Score II πŸ”’

DifficultyMedium

Description

Given an array nums, you have to get the maximum score starting from index 0 and hopping until you reach the last element of the array.

In each hop, you can jump from index i to an index j > i, and you get a score of (j - i) * nums[j].

Return the maximum score you can get.

 

Example 1:

Input: nums = [1,5,8]

Output: 16

Explanation:

There are two possible ways to reach the last element:

  • 0 -> 1 -> 2 with a score of (1 - 0) * 5 + (2 - 1) * 8 = 13.
  • 0 -> 2 with a score of (2 - 0) * 8 = 16.

Example 2:

Input: nums = [4,5,2,8,9,1,3]

Output: 42

Explanation:

We can do the hopping 0 -> 4 -> 6 with a score of (4 - 0) * 9 + (6 - 4) * 3 = 42.

 

Constraints:

  • 2 <= nums.length <= 105
  • 1 <= nums[i] <= 105

Solutions

Solution 1: Monotonic Stack

Thinking

The jump score is the same as Maximum Array Hopping Score I, but the limits rule out quadratic DP. The optimum is still to jump to the next value no smaller than the current one.

A decreasing stack extracts that index chain; from \(0\), add \(\textit{nums}[j]\times(j-i)\) along the stack. The time is linear and needs no memoization.

We observe that for the current position \(i\), we should jump to the next position \(j\) with the maximum value to obtain the maximum score.

Therefore, we traverse the array \(\textit{nums}\), maintaining a stack \(\textit{stk}\) that is monotonically decreasing from the bottom to the top of the stack. For the current position \(i\) being traversed, if the value corresponding to the top element of the stack is less than or equal to \(\textit{nums}[i]\), we continuously pop the top element of the stack until the stack is empty or the value corresponding to the top element of the stack is greater than \(\textit{nums}[i]\), and then push \(i\) into the stack.

Next, we initialize the answer \(\textit{ans}\) and the current position \(i = 0\), traverse the elements in the stack, each time taking out the top element \(j\), updating the answer \(\textit{ans} += \textit{nums}[j] \times (j - i)\), and then updating \(i = j\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def maxScore(self, nums: List[int]) -> int:
        stk = []
        for i, x in enumerate(nums):
            while stk and nums[stk[-1]] <= x:
                stk.pop()
            stk.append(i)
        ans = i = 0
        for j in stk:
            ans += nums[j] * (j - i)
            i = j
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public long maxScore(int[] nums) {
        Deque<Integer> stk = new ArrayDeque<>();
        for (int i = 0; i < nums.length; ++i) {
            while (!stk.isEmpty() && nums[stk.peek()] <= nums[i]) {
                stk.pop();
            }
            stk.push(i);
        }
        long ans = 0, i = 0;
        while (!stk.isEmpty()) {
            int j = stk.pollLast();
            ans += (j - i) * nums[j];
            i = j;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    long long maxScore(vector<int>& nums) {
        vector<int> stk;
        for (int i = 0; i < nums.size(); ++i) {
            while (stk.size() && nums[stk.back()] <= nums[i]) {
                stk.pop_back();
            }
            stk.push_back(i);
        }
        long long ans = 0, i = 0;
        for (int j : stk) {
            ans += (j - i) * nums[j];
            i = j;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func maxScore(nums []int) (ans int64) {
    stk := []int{}
    for i, x := range nums {
        for len(stk) > 0 && nums[stk[len(stk)-1]] <= x {
            stk = stk[:len(stk)-1]
        }
        stk = append(stk, i)
    }
    i := 0
    for _, j := range stk {
        ans += int64((j - i) * nums[j])
        i = j
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
function maxScore(nums: number[]): number {
    const stk: number[] = [];
    for (let i = 0; i < nums.length; ++i) {
        while (stk.length && nums[stk.at(-1)!] <= nums[i]) {
            stk.pop();
        }
        stk.push(i);
    }
    let ans = 0;
    let i = 0;
    for (const j of stk) {
        ans += (j - i) * nums[j];
        i = j;
    }
    return ans;
}

Comments