Maximum Array Hopping Score II

Problem

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.

Examples

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

Solution

Method 1 – Monotonic Stack Optimization (Right-to-Left)

Intuition

This is a variant of the first hopping problem, but we want to optimize the O(n^2) DP. Since the score for hopping from i to j is (j-i)*nums[j] + dp[j], and nums[j] is the only variable, we can use a monotonic stack to keep track of the best future hops efficiently.

Approach

1. Initialize a dp array of size n, where dp[i] is the max score starting from i.
2. Set dp[n-1] = 0 (no hops from the last index).
3. Use a monotonic decreasing stack to keep track of indices with higher nums[j] + dp[j]/(j-i).
4. For i from n-2 downto 0:
   • For each j in the stack, compute (j-i)*nums[j] + dp[j] and keep the max.
   • Maintain the stack so that only useful indices remain.
5. The answer is dp[0].

Code

C++

class Solution {
public:
    int maxScore(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 0);
        vector<int> st;
        dp[n-1] = 0;
        st.push_back(n-1);
        for (int i = n-2; i >= 0; --i) {
            int best = 0;
            for (int j : st) {
                best = max(best, (j-i)*nums[j] + dp[j]);
            }
            dp[i] = best;
            while (!st.empty() && nums[i] >= nums[st.back()]) st.pop_back();
            st.push_back(i);
        }
        return dp[0];
    }
};

Go

func maxScore(nums []int) int {
    n := len(nums)
    dp := make([]int, n)
    st := []int{n-1}
    for i := n-2; i >= 0; i-- {
        best := 0
        for _, j := range st {
            if v := (j-i)*nums[j]+dp[j]; v > best {
                best = v
            }
        }
        dp[i] = best
        for len(st) > 0 && nums[i] >= nums[st[len(st)-1]] {
            st = st[:len(st)-1]
        }
        st = append(st, i)
    }
    return dp[0]
}

Java

class Solution {
    public int maxScore(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Deque<Integer> st = new ArrayDeque<>();
        st.push(n-1);
        for (int i = n-2; i >= 0; --i) {
            int best = 0;
            for (int j : st) {
                best = Math.max(best, (j-i)*nums[j] + dp[j]);
            }
            dp[i] = best;
            while (!st.isEmpty() && nums[i] >= nums[st.peek()]) st.pop();
            st.push(i);
        }
        return dp[0];
    }
}

Kotlin

class Solution {
    fun maxScore(nums: IntArray): Int {
        val n = nums.size
        val dp = IntArray(n)
        val st = ArrayDeque<Int>()
        st.addLast(n-1)
        for (i in n-2 downTo 0) {
            var best = 0
            for (j in st) {
                best = maxOf(best, (j-i)*nums[j] + dp[j])
            }
            dp[i] = best
            while (st.isNotEmpty() && nums[i] >= nums[st.last()]) st.removeLast()
            st.addLast(i)
        }
        return dp[0]
    }
}

Python

class Solution:
    def maxScore(self, nums: list[int]) -> int:
        n = len(nums)
        dp = [0]*n
        st = [n-1]
        for i in range(n-2, -1, -1):
            best = 0
            for j in st:
                best = max(best, (j-i)*nums[j] + dp[j])
            dp[i] = best
            while st and nums[i] >= nums[st[-1]]:
                st.pop()
            st.append(i)
        return dp[0]

Rust

impl Solution {
    pub fn max_score(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut dp = vec![0; n];
        let mut st = vec![n-1];
        for i in (0..n-1).rev() {
            let mut best = 0;
            for &j in &st {
                best = best.max((j as i32 - i as i32)*nums[j] + dp[j]);
            }
            dp[i] = best;
            while let Some(&last) = st.last() {
                if nums[i] >= nums[last] {
                    st.pop();
                } else {
                    break;
                }
            }
            st.push(i);
        }
        dp[0]
    }
}

TypeScript

class Solution {
    maxScore(nums: number[]): number {
        const n = nums.length;
        const dp = new Array(n).fill(0);
        const st = [n-1];
        for (let i = n-2; i >= 0; --i) {
            let best = 0;
            for (const j of st) {
                best = Math.max(best, (j-i)*nums[j] + dp[j]);
            }
            dp[i] = best;
            while (st.length && nums[i] >= nums[st[st.length-1]]) st.pop();
            st.push(i);
        }
        return dp[0];
    }
}

Complexity

• ⏰ Time complexity: O(n^2) worst case, but often much better due to the stack pruning.
• 🧺 Space complexity: O(n), for the dp array and stack.