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:

1
2
3
4
5
6

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:

1
2
3
4
5

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

Solution

Method 1 – Dynamic Programming (Right-to-Left)

Intuition

We want the maximum score to reach the last index by hopping from earlier indices. For each index, we can hop to any later index, and the score is (j-i)*nums[j]. We can use dynamic programming from right to left, where dp[i] is the best score starting from i. For each i, try all possible j > i and take the best.

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. For i from n-2 downto 0:
    • For each j in (i+1, n):
      • dp[i] = max(dp[i], (j-i)*nums[j] + dp[j])
  4. The answer is dp[0].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    int maxScore(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 0);
        for (int i = n-2; i >= 0; --i) {
            for (int j = i+1; j < n; ++j) {
                dp[i] = max(dp[i], (j-i)*nums[j] + dp[j]);
            }
        }
        return dp[0];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func maxScore(nums []int) int {
    n := len(nums)
    dp := make([]int, n)
    for i := n-2; i >= 0; i-- {
        for j := i+1; j < n; j++ {
            if dp[i] < (j-i)*nums[j]+dp[j] {
                dp[i] = (j-i)*nums[j]+dp[j]
            }
        }
    }
    return dp[0]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public int maxScore(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        for (int i = n-2; i >= 0; --i) {
            for (int j = i+1; j < n; ++j) {
                dp[i] = Math.max(dp[i], (j-i)*nums[j] + dp[j]);
            }
        }
        return dp[0];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun maxScore(nums: IntArray): Int {
        val n = nums.size
        val dp = IntArray(n)
        for (i in n-2 downTo 0) {
            for (j in i+1 until n) {
                dp[i] = maxOf(dp[i], (j-i)*nums[j] + dp[j])
            }
        }
        return dp[0]
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def maxScore(self, nums: list[int]) -> int:
        n = len(nums)
        dp = [0]*n
        for i in range(n-2, -1, -1):
            for j in range(i+1, n):
                dp[i] = max(dp[i], (j-i)*nums[j] + dp[j])
        return dp[0]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
    pub fn max_score(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut dp = vec![0; n];
        for i in (0..n-1).rev() {
            for j in i+1..n {
                dp[i] = dp[i].max((j as i32 - i as i32)*nums[j] + dp[j]);
            }
        }
        dp[0]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

Complexity

  • ⏰ Time complexity: O(n^2), since for each i, we check all j > i.
  • 🧺 Space complexity: O(n), for the dp array.