Problem Description

You have an integer array nums with length n. You start at index 0 and need to reach index n - 1 by making jumps.

From any index i, you can only jump to indices that are greater than i (you can only jump forward).

When you jump from index i to index j, you earn a score calculated as: (j - i) * nums[i]

Your task is to find the maximum possible total score you can achieve by the time you reach the last index.

For example, if you jump from index i to index j, the score for that jump is the distance between the indices (j - i) multiplied by the value at the starting position nums[i]. You accumulate these scores for all jumps you make until reaching the final index.

The key insight is that jumping from index i to index j with score (j - i) * nums[i] is equivalent to taking j - i steps, where each step contributes nums[i] to your score. This means if you encounter a larger value later, it's beneficial to start using that larger value for subsequent steps to maximize your total score.

Intuition

Let's think about what happens when we make jumps. If we jump from index i to index j, we get a score of (j - i) * nums[i]. This can be reinterpreted as: we're taking j - i steps, and each step gives us nums[i] points.

Now imagine we're at index i with value nums[i], and we need to decide where to jump next. If we jump to index j and then to index k, our total score would be:

• Jump from i to j: (j - i) * nums[i]
• Jump from j to k: (k - j) * nums[j]
• Total: (j - i) * nums[i] + (k - j) * nums[j]

But what if we jumped directly from i to k? We'd get:

• Jump from i to k: (k - i) * nums[i]

Comparing these two approaches, the difference is:

• Direct jump: (k - i) * nums[i]
• Two jumps: (j - i) * nums[i] + (k - j) * nums[j]

Notice that (k - i) * nums[i] = (j - i) * nums[i] + (k - j) * nums[i]. So the two-jump approach gives us (k - j) * nums[j] while the direct jump would give us (k - j) * nums[i] for that portion.

This reveals the key insight: we should only jump to a new position if its value is greater than our current value. Otherwise, we're better off "staying" with our current value (conceptually continuing to use it for scoring).

This leads to a greedy strategy: as we traverse the array, we keep track of the maximum value we've seen so far. Each step forward contributes this maximum value to our total score, because we're essentially "using" the best value we've encountered for each unit of distance we travel.

Learn more about Greedy patterns.

Solution Approach

Based on our intuition that we should always use the maximum value encountered so far for scoring each step, we can implement a greedy solution.

The algorithm works as follows:

1. Initialize variables: We maintain two variables:

   • ans: accumulates the total score
   • mx: tracks the maximum value seen so far

2. Traverse the array: We iterate through the array from index 0 to n-2 (excluding the last element since we don't need to jump from the last position).

3. For each position:

   • Update mx to be the maximum between the current mx and the current element nums[i]
   • Add mx to our answer ans

The key insight is that each step forward (from position i to i+1) contributes exactly mx to our score, where mx is the best value we've encountered up to that point.

Let's trace through why this works:

• When we move from position i to position i+1, we're effectively taking one step
• This step contributes the maximum value we've seen so far to our score
• By accumulating mx for each step until we reach the last position, we get the maximum possible score

The implementation in code:

class Solution:
    def findMaximumScore(self, nums: List[int]) -> int:
        ans = mx = 0
        for x in nums[:-1]:  # Iterate until second-to-last element
            mx = max(mx, x)   # Update maximum value seen
            ans += mx         # Add maximum to total score
        return ans

This greedy approach ensures we always use the best available value for each unit of distance traveled, resulting in the maximum possible total score. The time complexity is O(n) as we traverse the array once, and the space complexity is O(1) as we only use two variables.

Example Walkthrough

Let's walk through the solution with a concrete example to understand how the greedy approach works.

Example: nums = [1, 3, 1, 5]

We need to reach index 3 starting from index 0. Let's trace through the algorithm:

Initial state:

• ans = 0 (total score)
• mx = 0 (maximum value seen so far)
• We'll process indices 0, 1, and 2 (excluding the last element)

Step 1: Process index 0 (value = 1)

• Update mx = max(0, 1) = 1
• Add to score: ans = 0 + 1 = 1
• This represents moving from position 0 to position 1, using value 1

Step 2: Process index 1 (value = 3)

• Update mx = max(1, 3) = 3
• Add to score: ans = 1 + 3 = 4
• This represents moving from position 1 to position 2, now using the better value 3

Step 3: Process index 2 (value = 1)

• Update mx = max(3, 1) = 3 (keeps 3 since it's larger)
• Add to score: ans = 4 + 3 = 7
• This represents moving from position 2 to position 3, still using value 3

Final Result: ans = 7

Why this is optimal: Let's verify by considering the actual jumps this represents:

• We conceptually jump from index 1 (value 3) directly to index 3
• Score for this jump: (3 - 1) * 3 = 2 * 3 = 6
• Plus the initial move from index 0 to index 1: (1 - 0) * 1 = 1
• Total: 6 + 1 = 7 ✓

The algorithm correctly identifies that once we encounter the value 3 at index 1, we should "use" that value for all subsequent steps since it's larger than what comes after (the 1 at index 2). This maximizes our total score.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. The algorithm iterates through the array once (excluding the last element with nums[:-1]), performing constant-time operations (max() comparison and addition) for each element.

The space complexity is O(1). The algorithm only uses two variables (ans and mx) to store intermediate results, regardless of the input size. No additional data structures are created that scale with the input.

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

Common Pitfalls

Pitfall 1: Misunderstanding the Jump Mechanics

The Problem: Many people initially interpret this as a dynamic programming problem where you need to explicitly track which indices to jump to. They might try to enumerate all possible jump sequences and calculate scores for each, leading to unnecessary complexity.

Why It Happens: The problem statement mentions "jumping from index i to index j" which naturally leads to thinking about explicit jump decisions and paths through the array.

The Solution: Recognize that jumping from index i to index j with score (j - i) * nums[i] is mathematically equivalent to taking j - i unit steps, where each step contributes nums[i] to the score. This reframing allows us to think of it as: "for each unit of distance traveled, what's the best value we can use?"

Pitfall 2: Including the Last Element in Iteration

The Problem: Accidentally iterating through all elements including nums[n-1]:

# Incorrect
for num in nums:  # This includes the last element
    max_value = max(max_value, num)
    total_score += max_value

Why It Happens: It's natural to want to process all elements in the array, and forgetting that we don't need to "jump from" the last position since we're already at the destination.

The Solution: Always exclude the last element from iteration using slicing nums[:-1] or explicit range range(len(nums) - 1). The last element doesn't contribute to the score because we've already reached our destination.

Pitfall 3: Overthinking the Greedy Choice

The Problem: Doubting whether the greedy approach is optimal and trying to find counterexamples where using a smaller value earlier might lead to a better overall score.

Why It Happens: Greedy algorithms don't always work, and it's good instinct to be skeptical. One might think: "What if I save the maximum value for later jumps?"

The Solution: Understand that once you've seen a value, you can use it for all subsequent steps. There's no benefit to "saving" a good value for later because you can start using it immediately and continue using it. The key insight is that every unit of forward progress needs to be scored by some value, and using the maximum available value for each unit is always optimal.