#3282

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Reach End of Array With Max Score

Calculate the maximum score to reach the end of an array using greedy jumps based on array values and distances.

Problem Statement

You are given an integer array nums of length n. Starting at index 0, you must reach the last index n - 1 by jumping only to indices greater than your current position.

Each jump from index i to index j earns a score calculated as (j - i) * nums[i]. Determine the sequence of jumps that maximizes the total score from start to finish, respecting the greedy choice and invariant that each jump should optimally advance toward higher cumulative score.

Examples

Example 1

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

Output: 7

First, jump to index 1 and then jump to the last index. The final score is 1 * 1 + 2 * 3 = 7 .

Example 2

Input: nums = [4,3,1,3,2]

Output: 16

Jump directly to the last index. The final score is 4 * 4 = 16 .

Constraints

1 <= nums.length <= 105
1 <= nums[i] <= 105

Solution Approach

Greedy Selection of Next Jump

At each index, evaluate all reachable indices j > i and select the one that maximizes (j - i) * nums[i]. This local greedy choice ensures the optimal score path while preserving the invariant for future steps.

Dynamic Tracking of Maximum Score

Maintain an array or data structure to store the maximum score obtainable from each index. Update it iteratively as you compute the greedy jumps to ensure the running total score is always maximized.

Efficient Skipping Using Monotonic Queue

Use a monotonic queue to efficiently identify the next optimal jump index without checking all possibilities, reducing unnecessary comparisons and keeping the greedy selection process linear in practice.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity can range from O(n^2) for naive evaluation to O(n) with a monotonic queue or optimized approach. Space complexity is O(n) for storing scores or O(1) if using in-place tracking with a pointer strategy.

What Interviewers Usually Probe

Candidate attempts all jumps naively without leveraging greedy invariant.
Candidate fails to maintain cumulative maximum score while iterating.
Candidate overlooks distance multiplier in scoring, reducing total score.

Common Pitfalls or Variants

Common pitfalls

Forgetting to multiply the jump distance by nums[i], leading to incorrect score.
Selecting a local maximum without considering future cumulative impact.
Inefficiently scanning all indices, causing timeouts on large arrays.

Follow-up variants

Compute maximum score when jumps can skip backward but still maximize total.
Modify scoring to use sum of nums[i] instead of distance multiplier.
Restrict jumps to fixed-length steps and find maximum achievable score.

FAQ

What is the core pattern in Reach End of Array With Max Score?

The core pattern is greedy choice plus invariant validation: always jump to the index that maximizes cumulative score while preserving optimal substructure.

How do I calculate the score for each jump?

Each jump from index i to index j earns a score of (j - i) * nums[i], factoring in both distance and current element value.

Can I jump backwards or skip indices arbitrarily?

No, jumps must go to indices greater than the current index; backward jumps violate the problem constraints.

What common mistakes should I avoid?

Avoid ignoring the distance multiplier, choosing local maxima without cumulative check, and iterating inefficiently over all indices.

Is there an efficient way to solve large arrays?

Yes, using a monotonic queue or dynamic tracking allows linear or near-linear time computation while maintaining the greedy invariant.

terminal

Solution

Solution 1: Greedy

Suppose we jump from index $i$ to index $j$, then the score is $(j - i) \times \text{nums}[i]$. This is equivalent to taking $j - i$ steps, and each step earns a score of $\text{nums}[i]$. Then we continue to jump from $j$ to the next index $k$, and the score is $(k - j) \times \text{nums}[j]$, and so on. If $\text{nums}[i] \gt \text{nums}[j]$, then we should not jump from $i$ to $j$, because the score obtained this way is definitely less than the score obtained by jumping directly from $i$ to $k$. Therefore, each time we should jump to the next index with a value greater than the current index.

1

2

3

4

5

6

7

class Solution:
    def findMaximumScore(self, nums: List[int]) -> int:
        ans = mx = 0
        for x in nums[:-1]:
            mx = max(mx, x)
            ans += mx
        return ans

Continue Practicing

#3281 maximize score of numbers in ranges #3273 minimum amount of damage dealt to bob #3296 minimum number of seconds to make mountain height zero