LeetCode Problem 3282

Difficulty: 🟡 Medium
Topics: Array, Greedy

Solution

LeetCode 3282 - Reach End of Array With Max Score

Problem Understanding

We are given an integer array nums, where each position represents a possible jump starting point. We begin at index 0 and must eventually reach index n - 1.

From any index i, we may jump to any later index j where j > i. The score earned from that jump is:

$(j-i)\cdot nums[i]$

The total score is the sum of the scores from all jumps taken along the path.

The task is to maximize the total score when reaching the last index.

The important detail is that the jump score depends only on:

• the jump distance (j - i)
• the value at the starting position nums[i]

The destination value does not directly contribute to the score of that jump.

For example, suppose:

nums = [1,3,1,5]

If we jump:

• from index 0 to 1, we gain 1 * 1 = 1
• from index 1 to 3, we gain 2 * 3 = 6

Total score = 7.

The constraints are important:

• n can be as large as 100000
• values can also be large

This immediately tells us that any quadratic solution will be too slow. We need something close to linear time.

A few important observations and edge cases:

• If the array length is 1, we are already at the destination, so the score is 0.
• Large jumps are sometimes optimal because multiplying a large distance by a large value can dominate smaller intermediate jumps.
• However, taking multiple jumps can sometimes increase the score if we can move onto a larger value early.
• Since all values are positive, every additional step contributes positively to the score.

Approaches

Brute Force Approach

A natural first idea is dynamic programming.

Define:

dp[i] = maximum score achievable when reaching index i

Then for every index i, try all previous positions j < i:

dp[i] = max(dp[j] + (i - j) * nums[j])

This is correct because every valid path to i must end with some jump from an earlier position j.

However, this requires checking all pairs (j, i).

With n = 100000, an O(n^2) solution is far too slow.

Key Insight

The crucial observation is that every position contributes its value multiplied by how long we stay "using" that value before moving to a better one.

Suppose we are currently at index i.

If there exists a later index with a larger value, it is always beneficial to switch to that larger value as early as possible, because future distances multiplied by a larger number produce larger gains.

This leads to a greedy strategy:

• Maintain the maximum value seen so far while traversing the array.
• For every step between adjacent indices, add the best value available so far.

Another way to think about it:

Moving from index k to k + 1 contributes exactly the value of whichever index we most recently jumped from.

So instead of thinking in terms of large jumps, we can think of traversing the array one step at a time while always using the largest value encountered so far.

This produces a simple linear solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force DP	O(n²)	O(n)	Tries every possible previous jump
Optimal Greedy	O(n)	O(1)	Maintains best value seen so far

Algorithm Walkthrough

1. Initialize a variable best with nums[0].

This represents the largest value available from any position we could currently be using for future movement. 2. Initialize score = 0.

This will accumulate the total maximum score. 3. Iterate through the array from index 1 to n - 1.

At every step, we conceptually move one position to the right. 4. Add best to the score.

Moving one step contributes the value of the best starting point available so far. 5. Update best.

If nums[i] is larger than the current best, future steps should use this larger value instead. 6. Continue until the last index is reached. 7. Return the accumulated score.

Why it works

Every movement across one edge between consecutive indices contributes the value of the chosen starting position.

If we split any jump into unit movements, the total contribution becomes:

$(j-i)\cdot nums[i]=\sum_{k=i}^{j-1} nums[i]$

For every unit step, the optimal choice is to use the maximum value available among previously visited indices. Therefore, greedily maintaining the largest value seen so far guarantees the maximum possible contribution for every future step.

Python Solution

from typing import List

class Solution:
    def findMaximumScore(self, nums: List[int]) -> int:
        n = len(nums)

        if n == 1:
            return 0

        best = nums[0]
        total_score = 0

        for i in range(1, n):
            total_score += best
            best = max(best, nums[i])

        return total_score

The implementation directly follows the greedy observation.

We first handle the edge case where the array has only one element. In that situation, no jumps are needed, so the score is zero.

The variable best stores the maximum value encountered so far. Initially, this is nums[0].

As we iterate from left to right, every move from index i - 1 to i contributes the current best value to the answer. After processing the step, we update best if the current element is larger.

Because each index is processed exactly once, the solution runs in linear time.

Go Solution

func findMaximumScore(nums []int) int64 {
	n := len(nums)

	if n == 1 {
		return 0
	}

	best := nums[0]
	var totalScore int64 = 0

	for i := 1; i < n; i++ {
		totalScore += int64(best)

		if nums[i] > best {
			best = nums[i]
		}
	}

	return totalScore
}

The Go implementation is nearly identical to the Python version.

One important detail is integer overflow. Since the score can become quite large, the function returns int64, and accumulation is performed using int64.

Slices in Go naturally handle dynamic array access, so no special handling is required.

Worked Examples

Example 1

nums = [1,3,1,5]

Initial state:

Step	Index	best	Added Score	Total
Start	0	1	0	0

Process index 1:

• Add current best = 1
• Total becomes 1
• Update best = max(1, 3) = 3

Step	Index	best	Added Score	Total
1	1	3	1	1

Process index 2:

• Add current best = 3
• Total becomes 4
• best remains 3

Step	Index	best	Added Score	Total
2	2	3	3	4

Process index 3:

• Add current best = 3
• Total becomes 7
• Update best = 5

Step	Index	best	Added Score	Total
3	3	5	3	7

Final answer:

7

Example 2

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

Initial state:

Step	Index	best	Added Score	Total
Start	0	4	0	0

Process index 1:

• Add 4
• Total = 4

Process index 2:

• Add 4
• Total = 8

Process index 3:

• Add 4
• Total = 12

Process index 4:

• Add 4
• Total = 16

Step	Index	best	Added Score	Total
Final	4	4	4	16

Final answer:

16

This corresponds to jumping directly from index 0 to index 4.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed once
Space	O(1)	Only a few variables are used

The algorithm performs a single pass through the array. No nested loops or auxiliary data structures are required. Therefore, the running time is linear and the extra space usage is constant.

Test Cases

sol = Solution()

assert sol.findMaximumScore([1,3,1,5]) == 7  # Provided example
assert sol.findMaximumScore([4,3,1,3,2]) == 16  # Direct jump optimal

assert sol.findMaximumScore([5]) == 0  # Single element

assert sol.findMaximumScore([1,1,1,1]) == 3  # Uniform values

assert sol.findMaximumScore([1,2,3,4,5]) == 14  # Increasing sequence

assert sol.findMaximumScore([5,4,3,2,1]) == 20  # Decreasing sequence

assert sol.findMaximumScore([2,10,1,1,1]) == 32  # Early large value dominates

assert sol.findMaximumScore([1,100,1,100,1]) == 301  # Multiple large peaks

assert sol.findMaximumScore([100000] * 100000) == 9999900000  # Large stress case

assert sol.findMaximumScore([3,1,5,2,6]) == 19  # Multiple updates to best

Test Summary

Test	Why
[1,3,1,5]	Verifies sample case with intermediate jump
[4,3,1,3,2]	Verifies direct jump behavior
[5]	Smallest possible input
[1,1,1,1]	Equal values throughout
[1,2,3,4,5]	Strictly increasing values
[5,4,3,2,1]	Strictly decreasing values
[2,10,1,1,1]	Large value appears early
[1,100,1,100,1]	Multiple dominant peaks
Large repeated values	Stress test for performance and overflow
[3,1,5,2,6]	Tests repeated best updates

Edge Cases

One important edge case is an array with only one element. Since we already start at the last index, no movement is required and the answer must be zero. A careless implementation might incorrectly add the starting value or attempt invalid iteration. The implementation handles this explicitly with an early return.

Another important case is a strictly decreasing array such as [5,4,3,2,1]. In this situation, the first value always remains the best choice for all future movement. The algorithm correctly preserves best = 5 throughout the traversal and accumulates the optimal score.

A third important edge case is a strictly increasing array such as [1,2,3,4,5]. Here, the best value changes repeatedly as we move through the array. The greedy update step ensures that each newly discovered larger value becomes the contributor for all future positions.

Large inputs are also important. Since n can be 100000, any quadratic approach would time out. The linear greedy solution processes each element exactly once and uses constant extra memory, making it efficient enough for the largest allowed constraints.