LeetCode 3221 - Maximum Array Hopping Score II

The problem gives us an integer array nums, where each position represents a possible location we can stand on. We always begin at index 0, and we must eventually reach the last index of the array. From any index i, we are allowed to jump to any later index j where j i.

leetcodemediumarraystackgreedymonotonic-stack

LeetCode Problem 3221

Difficulty: 🟡 Medium
Topics: Array, Stack, Greedy, Monotonic Stack

Solution

LeetCode 3221 - Maximum Array Hopping Score II

Problem Understanding

The problem gives us an integer array nums, where each position represents a possible location we can stand on. We always begin at index 0, and we must eventually reach the last index of the array.

From any index i, we are allowed to jump to any later index j where j > i. Every jump contributes a score equal to:

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

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

Our goal is to choose a sequence of jumps that maximizes the total score.

The important detail is that the score of a jump depends only on two things:

  1. The distance traveled, (j - i)
  2. The value at the destination index, nums[j]

The value at the starting index does not matter for the jump score.

For example, if we jump from index 2 to index 5, the contribution is:

$$(5 - 2) \times nums[5]$$

We may take many small jumps or a few large jumps. The challenge is determining which combination produces the largest total score.

The constraints are important:

  • nums.length can be as large as 10^5
  • Each value can also be as large as 10^5

Because the input size is large, any quadratic solution with nested loops will be too slow. We need a linear or near linear approach.

Several edge cases are worth noticing immediately:

  • Arrays of length 2, where there is only one possible jump.
  • Strictly increasing arrays, where delaying jumps may be beneficial.
  • Strictly decreasing arrays, where frequent hopping may produce a larger score.
  • Arrays with repeated values, where multiple jump choices may appear equivalent.
  • Very large values, where integer overflow matters in languages like Go.

The problem guarantees:

  • The array always has at least two elements.
  • All values are positive integers.
  • A path to the end always exists because jumps can move to any later index.

Approaches

Brute Force Dynamic Programming

A straightforward approach is to define:

$$dp[i] = \text{maximum score achievable when reaching index } i$$

To compute dp[i], we try every previous index j < i:

$$dp[i] = \max(dp[j] + (i - j) \times nums[i])$$

This recurrence is correct because every valid path into i must come from some earlier position j.

The problem is performance. For every index i, we scan all previous indices. That leads to:

$$O(n^2)$$

With n = 10^5, this becomes far too slow.

Greedy Observation

The key insight is that each position contributes its value multiplied by how long we continue using it before switching to a better destination.

Suppose we are currently at index i. If there exists a later index with a larger value, then it is always beneficial to move to the first such larger value as soon as possible.

Why?

Assume:

  • nums[k] > nums[i]
  • We stay at i for some extra distance instead of switching to k

Every extra step using nums[i] earns a smaller multiplier than using nums[k].

So once a larger value becomes available, we should immediately switch to it.

This transforms the problem into maintaining the maximum value seen so far while traversing from left to right.

At every step between adjacent indices, the best value available so far contributes one segment of score.

Another way to interpret this:

Moving from left to right, every unit distance should be multiplied by the largest value encountered up to that point.

This produces a simple greedy linear solution.

Approach Comparison

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

Algorithm Walkthrough

Optimal Greedy Algorithm

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

This represents the largest value available among indices we could currently jump from. 2. Initialize total_score = 0.

This will accumulate the maximum possible score. 3. Traverse the array from index 1 to n - 1.

At each step, we are effectively moving one unit of distance to the right. 4. For every position i, add best_value to the answer.

Why does this work?

Moving from position i - 1 to i represents one unit of distance. That unit should be multiplied by the best value available so far, because we can always structure jumps so that this unit distance is attributed to the maximum reachable value. 5. After processing the contribution for position i, update:

best_value = max(best_value, nums[i])

This ensures future distance units use the largest value encountered so far. 6. After finishing the traversal, return total_score.

Why it works

The greedy invariant is:

At every unit of movement from left to right, the optimal contribution comes from the largest value encountered so far.

If a larger value appears later, switching to it immediately is always optimal because future distance units multiplied by a larger number produce a greater score.

Thus, every segment of distance should use the maximum value available at that point, and summing these contributions gives the optimal total score.

Python Solution

from typing import List

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        best_value = nums[0]
        total_score = 0

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

        return total_score

The implementation is extremely compact because the greedy observation removes the need for dynamic programming.

The variable best_value stores the maximum element encountered so far while scanning left to right.

For every step from one index to the next, we add the current best_value to total_score. This corresponds to assigning that unit of distance to the best available destination value.

After adding the contribution, we update best_value using the current array element. This ensures future distance units can benefit from newly discovered larger values.

The algorithm processes the array exactly once and uses constant extra memory.

Go Solution

func maxScore(nums []int) int64 {
    bestValue := nums[0]
    var totalScore int64 = 0

    for i := 1; i < len(nums); i++ {
        totalScore += int64(bestValue)

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

    return totalScore
}

The Go implementation follows the same greedy logic as the Python version.

One important difference is integer handling. Since the answer can exceed the range of a 32 bit integer, the return type is int64. Every contribution added to totalScore is explicitly converted to int64.

Go slices are used naturally for array traversal, and no additional data structures are required.

Worked Examples

Example 1

Input:

nums = [1, 5, 8]

We track:

  • best_value
  • total_score
Index nums[i] best_value before update Added to score total_score best_value after update
1 5 1 1 1 5
2 8 5 5 6 8

The greedy accumulation gives 6.

Now interpret it as jumps:

  • First unit distance uses value 1
  • Second unit distance uses value 5

Equivalent optimal path:

  • 0 -> 1, score = 1 * 5 = 5
  • 1 -> 2, score = 1 * 8 = 8

Total:

13

But we can do better:

  • 0 -> 2, score = 2 * 8 = 16

This reveals the true optimal formulation:

The correct greedy interpretation is actually based on future maximums, not prefix maximums.

So we need the maximum suffix value available for each distance segment.

Correct Greedy Insight

For every position i, we should use the largest value that appears after position i.

This means:

  • While traversing from left to right,
  • We should maintain the best future destination.

That leads to a monotonic stack or suffix maximum interpretation.

Correct Optimal Strategy

Suppose we are at index i.

If there exists a later index with a larger value, then directly jumping farther is always at least as good as stopping earlier at a smaller value.

Therefore, the optimal path only jumps to indices that are suffix maxima.

We can process the array from right to left and greedily determine the best jump chain.

Correct Python Solution

from typing import List

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

        stack = []

        for i in range(n - 1, -1, -1):
            while stack and nums[stack[-1]] <= nums[i]:
                stack.pop()

            stack.append(i)

        stack.reverse()

        score = 0

        for i in range(len(stack) - 1):
            left = stack[i]
            right = stack[i + 1]

            score += (right - left) * nums[right]

        return score

However, this still misses direct jump optimization.

The actual optimal solution is much simpler.

Observe:

For every index i, the best next jump is the index with maximum value among all future positions.

So we greedily jump to the farthest future maximum.

Final Correct Python Solution

from typing import List

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        n = len(nums)
        score = 0
        current = 0

        while current < n - 1:
            next_index = current + 1

            for j in range(current + 1, n):
                if nums[j] > nums[next_index]:
                    next_index = j

            score += (next_index - current) * nums[next_index]
            current = next_index

        return score

This greedy idea is correct conceptually but quadratic in the worst case.

We now optimize it using suffix maximums.

Final Optimal Python Solution

from typing import List

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

        next_best = [0] * n
        best_index = n - 1

        for i in range(n - 1, -1, -1):
            if nums[i] > nums[best_index]:
                best_index = i

            next_best[i] = best_index

        score = 0
        current = 0

        while current < n - 1:
            next_index = next_best[current + 1]
            score += (next_index - current) * nums[next_index]
            current = next_index

        return score

This version preprocesses suffix maximum indices in linear time.

Then, from every position, we immediately jump to the best future destination.

Final Optimal Go Solution

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

    nextBest := make([]int, n)
    bestIndex := n - 1

    for i := n - 1; i >= 0; i-- {
        if nums[i] > nums[bestIndex] {
            bestIndex = i
        }

        nextBest[i] = bestIndex
    }

    var score int64 = 0
    current := 0

    for current < n-1 {
        nextIndex := nextBest[current+1]

        score += int64(nextIndex-current) * int64(nums[nextIndex])

        current = nextIndex
    }

    return score
}

Worked Examples

Example 1

nums = [1, 5, 8]

Suffix maximum indices:

Index Best future index
0 2
1 2
2 2

Simulation:

Current Next Jump Contribution Total
0 2 (2 - 0) × 8 = 16 16

Answer:

16

Example 2

nums = [4, 5, 2, 8, 9, 1, 3]

Suffix maximum indices:

Index Best future index
0 4
1 4
2 4
3 4
4 4
5 6
6 6

Simulation:

Current Next Jump Contribution Total
0 4 4 × 9 = 36 36
4 6 2 × 3 = 6 42

Final answer:

42

Complexity Analysis

Measure Complexity Explanation
Time O(n) One pass for suffix preprocessing and one pass for jumps
Space O(n) Stores suffix maximum indices

The preprocessing step computes the best future destination for every index in linear time. The jumping phase also moves forward through the array once, so the total runtime remains linear.

The additional array next_best requires linear extra space.

Test Cases

sol = Solution()

assert sol.maxScore([1, 5, 8]) == 16  # direct jump is optimal
assert sol.maxScore([4, 5, 2, 8, 9, 1, 3]) == 42  # multiple jumps
assert sol.maxScore([1, 2]) == 2  # minimum length
assert sol.maxScore([10, 1, 1, 1]) == 3  # forced small values later
assert sol.maxScore([1, 1, 1, 1]) == 3  # equal values
assert sol.maxScore([5, 4, 3, 2, 1]) == 10  # decreasing sequence
assert sol.maxScore([1, 100, 1, 100]) == 300  # repeated large values
assert sol.maxScore([3, 7, 2, 9, 1]) == 27  # best large jump
assert sol.maxScore([100000, 100000]) == 100000  # large values
assert sol.maxScore([1, 3, 2, 5, 4, 6]) == 30  # multiple upgrades

Test Summary

Test Why
[1, 5, 8] Validates direct long jump
[4,5,2,8,9,1,3] Tests multiple optimal jumps
[1,2] Minimum valid size
[10,1,1,1] Large starting value
[1,1,1,1] Repeated equal values
[5,4,3,2,1] Strictly decreasing array
[1,100,1,100] Repeated maxima
[3,7,2,9,1] Intermediate best destination
[100000,100000] Large integer handling
[1,3,2,5,4,6] Multiple suffix maximum transitions

Edge Cases

Minimum Length Array

When the array length is exactly 2, there is only one possible jump, from index 0 to index 1.

A buggy implementation might overcomplicate the logic or accidentally skip processing because there are no intermediate positions.

The implementation handles this naturally because the loop immediately computes the single jump contribution.

Strictly Increasing Arrays

For arrays like:

[1, 2, 3, 4, 5]

The optimal strategy is often one large jump to the largest future value.

Naive greedy approaches that jump too early may lose score because later destinations have much larger multipliers.

The suffix maximum preprocessing guarantees we always jump to the best future value.

Repeated Values

Arrays with repeated values can expose bugs in tie handling.

For example:

[5, 5, 5, 5]

Different jump paths produce the same score.

The implementation correctly handles ties because suffix maxima remain valid regardless of which equal value is selected.

Strictly Decreasing Arrays

For arrays like:

[9, 8, 7, 6]

There is never a better future value.

Incorrect greedy strategies may attempt large jumps unnecessarily.

The algorithm still works because the suffix maximum for each position becomes the immediate next position, producing the optimal sequence of shorter jumps.