Skip to content

Practice Reach End of Array With Max Score

Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.

Medium#3282
LeetCode Problem

Reach End of Array With Max Score

Problem Statement

Start at position 0 and reach the final position of nums by jumping only to larger indices. A jump from i to j contributes (j - i) * nums[i]. Maximize the sum of all jump scores. Approach: Each unit of distance can use the largest value encountered before crossing that distance. Add the running maximum for positions 0 through n - 2. This corresponds to jumping through positions that establish a larger value, then jumping to the end. The final value earns no score because no jump starts there. The scan takes O(n) time and O(1) extra space; use a 64-bit total.

Source: Reach End of Array With Max Score on LeetCode. Use the original task for its coding environment and submissions.

Examples

# Example 1

Input
nums = [2,5,1,4]
Output
12
Explanation

Jump from 0 to 1 for 2 points, then from 1 to 3 for 10 points.

# Example 2

Input
nums = [6,2,1]
Output
12
Explanation

Jump directly from index 0 to index 2 for 2 * 6 points.

Constraints

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

How to solve Reach End of Array With Max Score

Original notes for interview preparation, written for this problem. Reviewed .

Key insight

Every unit of distance from index 0 to the last index is crossed by exactly one jump and earns the value at that jump's start, so the best plan pays each unit the largest value seen so far: the answer is the sum of running maximums over all positions except the last.

Why brute force is not enough

A dynamic program over all pairs i < j costs O(n^2), about 10^10 operations for n up to 100,000.

Approach

  1. Reframe the score: a jump from i to j contributes nums[i] once per unit step it covers, so the total is a sum over unit steps, each paid at the value of the index where its covering jump started.
  2. The unit step from p to p + 1 can only be paid by an index at or before p, so its best payment is the maximum of the prefix ending at p.
  3. The bound is achievable: jump to each index that strictly raises the prefix maximum, then to the end, so every unit step is paid by the current prefix maximum.
  4. Scan from index 0 to n - 2, maintaining the largest value seen and adding it to a 64-bit total; the invariant is that the total equals the best score for all unit steps processed so far.
  5. Return the total; the last element contributes nothing since no jump starts there.

Walkthrough of Example 1

nums = [2,5,1,4] → 12

  1. nums is [2,5,1,4]; positions 0 through 2 contribute and position 3 is the destination.
  2. Position 0: running maximum 2, total 2, paying for the step from 0 to 1.
  3. Position 1: running maximum rises to 5, total 7, paying for the step from 1 to 2.
  4. Position 2: value 1 does not beat 5, total 12.
  5. The total 12 matches jumping 0 to 1 for 1 times 2 and 1 to 3 for 2 times 5, the expected output.

Time and space

Time O(n) · Space O(1). One pass over the n elements with a running maximum and an accumulator; no auxiliary arrays.

Interview pitfalls

  • Including the last element in the sum; it is only a landing spot.
  • Returning a nonzero score for a single-element array; with no jump the answer is 0.
  • Overflow: n up to 10^5 and values up to 10^5 give totals near 10^10, beyond 32 bits.
  • Jumping to every local maximum or straight to the global maximum; the correct stops are strict prefix maximums.
  • Treating ties as new maximums when reconstructing the path; a tie needs no stop.

Follow-up questions interviewers ask

  • How would you reconstruct the sequence of indices achieving the maximum?
  • What changes if each jump is limited to at most d positions forward?
  • If the score were (j - i) times nums[j] instead, what does the optimal path look like?

Further reading on the technique: Greedy algorithm

Related LeetCode Problems

Practice more problems similar to Reach End of Array With Max Score.

Review your practice with PhantomCodeAI

After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.