# 3221. Maximum Array Hopping Score II ðŸ”’

## 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

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$.

• 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;
}
}

• 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;
}
};

• 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


• 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
}

• 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;
}