Problem Description

You are given an array nums and need to find the maximum score you can achieve by hopping through the array.

Starting from index 0, you can make hops to reach the last element of the array. In each hop, you can jump from your current index i to any index j where j > i (you can only jump forward to a higher index).

When you make a jump from index i to index j, you earn a score calculated as: (j - i) * nums[j]. This means your score for each jump is the distance jumped multiplied by the value at the destination index.

Your goal is to find the maximum total score possible by making a sequence of jumps from index 0 until you reach some element in the array. Note that you don't necessarily need to reach the very last element - you can stop at any index.

For example, if you have an array [1, 5, 3]:

• You could jump directly from index 0 to index 1, earning score (1 - 0) * 5 = 5
• Or jump from index 0 to index 2, earning score (2 - 0) * 3 = 6
• Or jump from index 0 to index 1 (score = 5), then from index 1 to index 2 (score = (2 - 1) * 3 = 3), for a total score of 8

The function should return the maximum score achievable through any valid sequence of jumps.

Intuition

When we start at index 0, we face a decision: which index should we jump to next? We could jump to index 1, or index 2, or any other index up to the last one. Each choice gives us an immediate score of (j - 0) * nums[j], but it also affects our future possibilities.

The key insight is that once we make a jump to some index j, we're now faced with the exact same type of problem - just starting from index j instead of index 0. This suggests a recursive structure: the maximum score from index i depends on the maximum scores we can achieve from all the indices we can jump to from i.

Think of it like this: if we're at index i, we need to consider all possible next jumps. For each potential jump to index j, we get:

• An immediate score of (j - i) * nums[j] from making that jump
• Plus whatever maximum score we can achieve starting from index j

This naturally leads us to define a recursive function dfs(i) that returns the maximum score achievable starting from index i. For any index i, we try all possible jumps to indices j > i, calculate the score for each possibility as (j - i) * nums[j] + dfs(j), and take the maximum.

The base case occurs when we're at an index where we can't jump anymore (or choose not to jump). In this case, the score is 0.

Since we might revisit the same index i through different paths of exploration, we use memoization to cache the results. Once we've calculated dfs(i) once, we can reuse that result whenever we need it again, avoiding redundant calculations.

Learn more about Stack, Greedy, Dynamic Programming and Monotonic Stack patterns.

Solution Approach

The solution implements a top-down dynamic programming approach using memoization search. Here's how the implementation works:

We define a recursive function dfs(i) that calculates the maximum score obtainable starting from index i. The function uses Python's @cache decorator to automatically memoize results, preventing redundant calculations.

The recursive logic:

For each call to dfs(i), we:

1. Generate all possible next positions j where j ranges from i + 1 to len(nums) - 1
2. For each valid jump position j, calculate the score as (j - i) * nums[j] + dfs(j)
   • (j - i) * nums[j] is the immediate score from jumping to position j
   • dfs(j) is the maximum score achievable from position j onwards
3. Take the maximum among all these possible scores

Implementation details:

The code uses a list comprehension to generate all possible scores:

[(j - i) * nums[j] + dfs(j) for j in range(i + 1, len(nums))]

The or [0] part handles the base case - when we're at the last index or choose not to jump anymore, the list comprehension produces an empty list. In this case, we return 0 as the score.

The max() function then selects the best score among all possibilities.

Time and Space Complexity:

• Each state i is computed only once due to memoization
• For each state, we explore up to n - i - 1 transitions
• This gives us O(n²) time complexity overall
• Space complexity is O(n) for the memoization cache and recursion stack

The solution starts by calling dfs(0) to find the maximum score starting from index 0, which is our answer.

Example Walkthrough

Let's walk through the solution with the array nums = [1, 5, 3, 2].

We start by calling dfs(0) to find the maximum score from index 0.

Step 1: Calculate dfs(0) From index 0, we can jump to indices 1, 2, or 3. We need to evaluate:

• Jump to index 1: score = (1-0) * nums[1] + dfs(1) = 1 * 5 + dfs(1) = 5 + dfs(1)
• Jump to index 2: score = (2-0) * nums[2] + dfs(2) = 2 * 3 + dfs(2) = 6 + dfs(2)
• Jump to index 3: score = (3-0) * nums[3] + dfs(3) = 3 * 2 + dfs(3) = 6 + dfs(3)

To complete this calculation, we need to find dfs(1), dfs(2), and dfs(3).

Step 2: Calculate dfs(1) From index 1, we can jump to indices 2 or 3:

• Jump to index 2: score = (2-1) * nums[2] + dfs(2) = 1 * 3 + dfs(2) = 3 + dfs(2)
• Jump to index 3: score = (3-1) * nums[3] + dfs(3) = 2 * 2 + dfs(3) = 4 + dfs(3)

Step 3: Calculate dfs(2) From index 2, we can only jump to index 3:

• Jump to index 3: score = (3-2) * nums[3] + dfs(3) = 1 * 2 + dfs(3) = 2 + dfs(3)

Step 4: Calculate dfs(3) Index 3 is the last element. We have no valid jumps, so dfs(3) = 0.

Step 5: Work backwards with computed values

Now we can substitute back:

• dfs(2) = max(2 + dfs(3)) = max(2 + 0) = 2
• dfs(1) = max(3 + dfs(2), 4 + dfs(3)) = max(3 + 2, 4 + 0) = max(5, 4) = 5
• dfs(0) = max(5 + dfs(1), 6 + dfs(2), 6 + dfs(3)) = max(5 + 5, 6 + 2, 6 + 0) = max(10, 8, 6) = 10

The maximum score is 10, achieved by jumping from index 0 → 1 (score: 5) → 2 (score: 3) → 3 (score: 2).

Note how memoization helps here: when calculating dfs(0) and dfs(1), we both need dfs(2). With memoization, we only compute it once and reuse the cached result.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n^2)

The recursive function dfs(i) explores all possible jumps from position i to any position j where j > i. For each position i, the function iterates through all positions from i+1 to n-1 (where n is the length of the array).

• From position 0: we check n-1 positions
• From position 1: we check n-2 positions
• From position 2: we check n-3 positions
• ...
• From position n-2: we check 1 position

The total number of operations is: (n-1) + (n-2) + (n-3) + ... + 1 = n(n-1)/2 = O(n^2)

Due to memoization with @cache, each state dfs(i) is computed only once. Since there are n possible states (one for each index), and computing each state requires O(n) work (iterating through remaining positions), the overall time complexity is O(n^2).

Space Complexity: O(n)

The space complexity consists of:

• Recursion stack: In the worst case, the recursion depth can be O(n) when we jump one position at a time (e.g., from 0 to 1, then 1 to 2, etc.)
• Memoization cache: The @cache decorator stores results for each unique value of i, which ranges from 0 to n-1, requiring O(n) space

Therefore, the total space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Problem - Not Considering Stopping Early

The Pitfall: Many developers initially assume they must reach the last index of the array, similar to classic "jump game" problems. This leads to incorrect solutions that force a path to nums[n-1], potentially missing better scores by stopping at an earlier index with a higher value.

Example of the Issue: Consider the array [1, 5, 2, 1]:

• Forcing to reach the end: Jump 0→1 (score: 5), then 1→3 (score: 2×1 = 2), total = 7
• Optimal solution: Jump 0→1 (score: 5) and stop, total = 5 (actually worse in this case)
• But for [1, 10, -5]: Stopping at index 1 gives score 10, while continuing to index 2 would give 10 + 1×(-5) = 5

The Fix: The provided solution correctly handles this by considering all possible jumps and naturally allowing the recursion to "stop" at any index (returning 0 when no more jumps yield positive benefit).

2. Integer Overflow with Large Arrays

The Pitfall: For large arrays with large values, the calculation (j - i) * nums[j] could potentially overflow in languages with fixed integer sizes. While Python handles arbitrary precision integers, this could be an issue when porting to other languages.

Example:

• Array length: 100,000
• nums[99999] = 10^9
• Jump from index 0 to 99999: 99,999 × 10^9 = ~10^14

The Fix: In Python, this isn't an issue due to automatic big integer handling. For other languages, consider:

• Using long/int64 data types
• Checking for overflow conditions
• Adding constraints validation

3. Stack Overflow with Deep Recursion

The Pitfall: Python has a default recursion limit (typically 1000). For large arrays, the recursive solution could hit this limit and raise a RecursionError.

Example: An array of length 5000 where the optimal path involves many small jumps could exceed Python's recursion limit.

The Fix: Convert to an iterative bottom-up DP approach:

def maxScore(self, nums: List[int]) -> int:
    n = len(nums)
    if n == 1:
        return 0
  
    # dp[i] = maximum score achievable starting from index i
    dp = [0] * n
  
    # Build the solution from right to left
    for i in range(n - 2, -1, -1):
        max_score = 0
        for j in range(i + 1, n):
            score = (j - i) * nums[j] + dp[j]
            max_score = max(max_score, score)
        dp[i] = max_score
  
    return dp[0]

4. Forgetting to Clear Cache Between Test Cases

The Pitfall: When using @cache on a nested function, the cache persists across multiple calls to the outer function. In competitive programming or testing environments where the same Solution instance is reused, this could lead to incorrect results if the input arrays have different lengths but similar indices.

The Fix: Either:

1. Create a new Solution instance for each test case
2. Use @lru_cache(maxsize=None) and manually clear it
3. Include array length or a unique identifier in the cache key
4. Use the iterative approach shown above which doesn't require caching