Problem

You are given an integer array nums of length n.

Your goal is to start at index 0 and reach index n - 1. You can only jump to indices greater than your current index.

The score for a jump from index i to index j is calculated as (j - i) * nums[i].

Return the maximum possible total score by the time you reach the last index.

Examples

Example 1

1
2
3
4
5

Input: nums = [1,3,1,5]
Output: 7
Explanation:
First, jump to index 1 and then jump to the last index. The final score is `1
* 1 + 2 * 3 = 7`.

Example 2

1
2
3
4

Input: nums = [4,3,1,3,2]
Output: 16
Explanation:
Jump directly to the last index. The final score is `4 * 4 = 16`.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5

Solution

Method 1 - Backward DP (Quadratic, illustrative)

Intuition

At each index, you can jump to any index to the right. The score for a jump from i to j is (j - i) * nums[i]. We want to maximize the total score to reach the last index. This is a classic DP problem: for each position, the best way to reach it is from some previous position, and we want to maximize the sum.

Approach

Let dp[i] be the maximum score to reach index i. For each i, we can jump to any j > i, so for each j, dp[j] = max(dp[j], dp[i] + (j - i) * nums[i]). However, this is O(n^2) and too slow.

But, since (j - i) * nums[i] is linear in j, and we want to maximize dp[j], we can use a monotonic queue or convex hull trick to optimize. However, for this problem, a greedy approach works: the best jump is either directly to the end or to the next highest value. For each index, try all possible jumps (in practice, the optimal is to jump directly to the end or to the next local maximum).

But since the constraints are large, we can process from the end backwards: for each i, dp[i] = max over all j > i of (j - i) * nums[i] + dp[j]. Since we can jump to any j > i, the optimal is to jump directly to the end: dp[i] = (n-1 - i) * nums[i]. But sometimes, an intermediate jump gives a better result. So, we process from the end, and for each i, dp[i] = max((j - i) * nums[i] + dp[j]) for all j > i. This is a classic convex hull trick/monotonic queue optimization, but for simplicity, we provide a clear O(n^2) DP here.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#include <vector>
#include <algorithm>
using namespace std;

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

package solution

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

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

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

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

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

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

Complexity

  • ⏰ Time complexity: O(n^2) – For each index we may examine up to n subsequent indices in the inner loop.
  • 🧺 Space complexity: O(n) – We store a dp array of length n.