LeetCode 3205 - Maximum Array Hopping Score I

The problem asks us to calculate the maximum score achievable by hopping through an array from the first element to the last. You start at index 0, and at each step, you can jump to any subsequent index j i. When you jump, you accumulate a score of (j - i) nums[j].

leetcodemediumarraydynamic-programmingstackgreedymonotonic-stack

LeetCode Problem 3205

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

Solution

Problem Understanding

The problem asks us to calculate the maximum score achievable by hopping through an array from the first element to the last. You start at index 0, and at each step, you can jump to any subsequent index j > i. When you jump, you accumulate a score of (j - i) * nums[j]. The goal is to select a sequence of jumps that maximizes the total score.

The input is an array of integers nums with length between 2 and 1000, and each element is between 1 and 100,000. The constraints indicate that an O(n^2) approach could be feasible for n ≈ 1000, but an O(n log n) or O(n) approach is preferable.

Important edge cases include arrays with all elements equal, strictly increasing or decreasing elements, and arrays of minimum length (2). The problem guarantees at least two elements, so we do not need to handle empty arrays.

Approaches

Brute Force

The naive approach is to explore every possible sequence of jumps. For each index i, try jumping to every j > i, recursively calculate the maximum score from j to the end, and add (j - i) * nums[j]. This method is correct because it considers every possible sequence of jumps, but it is extremely inefficient. For an array of size n, the number of possible jump sequences is exponential (O(2^n)), making this infeasible for n up to 1000.

Optimal Approach

The key observation is that the score from jumping to index j depends only on the previous maximum score and the formula (j - i) * nums[j]. We can formulate a dynamic programming solution where dp[j] stores the maximum score to reach index j. Instead of computing dp[j] by iterating over all previous i, we notice a monotonic property: if nums[i] is large, it may dominate smaller values of nums[i] even for smaller i. Using a monotonic stack or priority queue, we can efficiently determine the best previous index i for each j.

Specifically, we can maintain a stack of candidate indices where nums[i] - i or a derived linear function is monotonic. This reduces the inner loop computation from O(n) to amortized O(1) for each index, yielding an overall O(n) solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Recursively try every jump sequence
Optimal O(n) O(n) Use dynamic programming with a monotonic stack to efficiently find best previous index

Algorithm Walkthrough

  1. Initialize an array dp of size n, where dp[i] stores the maximum score to reach index i. Set dp[0] = 0 because we start at the first element.
  2. Create a monotonic stack to store candidate indices that could maximize future jumps.
  3. Iterate through the array from index 1 to n - 1.
  4. For each index j, remove indices from the stack that will never produce a higher score than the current candidate. This is done by comparing (dp[i] - i * nums[i]) values.
  5. Compute dp[j] as the maximum possible score from the top of the stack: dp[j] = (j - i) * nums[j] + dp[i] where i is the top index of the stack.
  6. Maintain the monotonic property of the stack by removing any indices that are now worse than j.
  7. After processing all indices, return dp[n - 1].

Why it works: The algorithm maintains an invariant that the stack contains only indices that could potentially maximize the score for future jumps. By keeping only relevant indices and removing dominated ones, we ensure the maximum score is always computed efficiently.

Python Solution

from typing import List

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0] * n
        stack = [0]  # store candidate indices

        for j in range(1, n):
            # Compute dp[j] using the top of the stack
            while len(stack) >= 2:
                i1, i2 = stack[-2], stack[-1]
                score1 = dp[i1] + (j - i1) * nums[j]
                score2 = dp[i2] + (j - i2) * nums[j]
                if score2 >= score1:
                    stack.pop(-2)  # remove the worse candidate
                else:
                    break
            dp[j] = dp[stack[-1]] + (j - stack[-1]) * nums[j]

            # Maintain monotonicity for future jumps
            while stack and (dp[j] - j * nums[j]) >= (dp[stack[-1]] - stack[-1] * nums[stack[-1]]):
                stack.pop()
            stack.append(j)

        return dp[-1]

Explanation: We initialize dp and a stack of candidate indices. For each j, we compute the maximum score achievable using the best index on the stack. We maintain the stack by removing dominated indices to ensure future indices are efficiently computed.

Go Solution

func maxScore(nums []int) int {
    n := len(nums)
    dp := make([]int, n)
    stack := []int{0}

    for j := 1; j < n; j++ {
        for len(stack) >= 2 {
            i1, i2 := stack[len(stack)-2], stack[len(stack)-1]
            score1 := dp[i1] + (j - i1) * nums[j]
            score2 := dp[i2] + (j - i2) * nums[j]
            if score2 >= score1 {
                stack = append(stack[:len(stack)-2], stack[len(stack)-1])
            } else {
                break
            }
        }
        dp[j] = dp[stack[len(stack)-1]] + (j - stack[len(stack)-1]) * nums[j]

        for len(stack) > 0 && (dp[j]-j*nums[j]) >= (dp[stack[len(stack)-1]]-stack[len(stack)-1]*nums[stack[len(stack)-1]]) {
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, j)
    }

    return dp[n-1]
}

Go Notes: The Go implementation mirrors Python closely. We use slices for the stack and carefully handle slice manipulation. Integer arithmetic is safe due to problem constraints.

Worked Examples

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

j stack dp[j] Calculation
1 [0] 5 0 + (1-0)*5
2 [1] 16 0 + (2-0)*8

Result: 16

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

j stack dp[j] Calculation
1 [0,1] 5 0 + (1-0)*5
2 [0,1,2] 9 1 + (2-1)*2
3 [3] 29 5 + (3-1)*8
4 [4] 41 29 + (4-3)*9
5 [4,5] 42 41 + (5-4)*1
6 [6] 42 41 + (6-4)*3

Result: 42

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each index is pushed/popped from stack at most once
Space O(n) dp array and stack of indices

The monotonic stack ensures that we do not iterate over all previous indices for every j, reducing naive O(n^2) complexity to O(n).

Test Cases

# Provided examples
assert Solution().maxScore([1,5,8]) == 16  # example 1
assert Solution().maxScore([4,5,2,8,9,1,3]) == 42  # example 2

# Edge cases
assert Solution().maxScore([1,1]) == 1  # minimum length
assert Solution().maxScore([100000,100000]) == 100000  # max values
assert Solution().maxScore([1,2,3,4,5]) == 16  # strictly increasing
assert Solution().maxScore([5,4,3,2,1]) == 9  # strictly decreasing
assert Solution().maxScore([1,3,1,3,1]) == 12  # alternating highs and lows
Test Why
[1,5,8] Basic small array example
[4,5,2,8,9,1,3] Complex sequence with skips
[1,1] Minimum length