LeetCode Solutions Blog

Maximum Array Hopping Score II

Number: 3529

Difficulty: Medium

Paid? Yes

Companies: Zluri

Problem Description

Given an array nums, you start at index 0 and want to reach the last element by making one or more “hops”. In each hop, you can jump from index i to an index j (with j > i) and earn a score equal to (j - i) * nums[j]. Your task is to compute the maximum score you can achieve when reaching the final element.

Key Insights

The problem is similar to jump game problems but with a score function weighted by both distance and the value at the destination.
A direct Dynamic Programming formulation leads to a recurrence: dp[j] = max{ dp[i] + (j - i) * nums[j] } for all i < j.
Rewriting the recurrence as dp[j] = j * nums[j] + max{ dp[i] - i * nums[j] } for i < j shows that for each j we need to query a function based on prior indices.
By viewing each candidate i as a “line” with slope = -i and intercept = dp[i], the query becomes a typical line query (Convex Hull Trick) where you want to maximize (line.slope * nums[j] + line.intercept).
Using a data structure that supports adding lines and querying for maximum values (for example, a LiChao tree) provides an efficient O(n log n) solution.

Space and Time Complexity

Time Complexity: O(n log n)
Space Complexity: O(n)

Solution

We solve this problem by maintaining an array dp where dp[j] represents the maximum score when reaching index j. We observe that the recurrence: dp[j] = j * nums[j] + max{ dp[i] - i * nums[j] } for all previous indices (i < j) can be interpreted as querying a set of lines, where each line corresponds to a previous index i and is defined by: line(x) = (-i) * x + dp[i] The query for each index j is made with x = nums[j], and then we update dp[j] accordingly by adding j * nums[j]. As we process the array from left to right, we add a new line for each index that can be used for future queries.

The algorithm uses a LiChao Tree (or a similar convex hull optimization data structure) that supports:

Inserting a line in O(log n)
Querying the maximum value among the stored lines in O(log n)

This approach ensures the overall time complexity is O(n log n) while using O(n) space for both the dp array and the LiChao tree.

Code Solutions

# Python implementation using LiChao Tree for Convex Hull Trick

import math

# Define the Line class representing a linear function: y = m * x + b
class Line:
    def __init__(self, m, b):
        self.m = m  # slope
        self.b = b  # intercept
    
    def value(self, x):
        return self.m * x + self.b

# LiChao Tree Node
class LiChaoNode:
    def __init__(self, l, r):
        self.left = None
        self.right = None
        self.l = l
        self.r = r
        self.line = None

class LiChaoTree:
    def __init__(self, x_min, x_max):
        self.root = LiChaoNode(x_min, x_max)
    
    def insert_line(self, new_line):
        # Insert new_line into the LiChao Tree
        def insert(node, new_line):
            l, r = node.l, node.r
            mid = (l + r) // 2
            
            if node.line is None:
                node.line = new_line
                return
            
            # Check which line is better at mid
            if new_line.value(mid) > node.line.value(mid):
                node.line, new_line = new_line, node.line
            
            # Decide which segment the new_line is better in
            if l == r:
                return
            if new_line.value(l) > node.line.value(l):
                if node.left is None:
                    node.left = LiChaoNode(l, mid)
                insert(node.left, new_line)
            elif new_line.value(r) > node.line.value(r):
                if node.right is None:
                    node.right = LiChaoNode(mid+1, r)
                insert(node.right, new_line)
        insert(self.root, new_line)
    
    def query(self, x):
        # Query maximum value at point x.
        def query_node(node, x):
            if node is None:
                return -math.inf
            res = node.line.value(x) if node.line is not None else -math.inf
            mid = (node.l + node.r) // 2
            if x <= mid:
                return max(res, query_node(node.left, x))
            else:
                return max(res, query_node(node.right, x))
        return query_node(self.root, x)

def max_hopping_score(nums):
    # Determine range for x used in queries (nums[j]), given nums[i] >= 1
    max_val = max(nums)  # maximum possible value in nums
    # Create LiChaoTree with domain [1, max_val]
    tree = LiChaoTree(1, max_val)
    
    n = len(nums)
    dp = [0] * n
    # Base case: starting at index 0, score is 0.
    # Insert line corresponding to index 0: slope = -0, intercept = dp[0] = 0.
    tree.insert_line(Line(-0, dp[0]))
    
    for j in range(1, n):
        # Query the LiChao Tree with x = nums[j]
        best = tree.query(nums[j])
        dp[j] = j * nums[j] + best
        # Insert the line for index j
        tree.insert_line(Line(-j, dp[j]))
    
    return dp[-1]

# Example Usage:
if __name__ == "__main__":
    # Example 1: nums = [1,5,8] should return 16
    print(max_hopping_score([1,5,8]))
    # Example 2: nums = [4,5,2,8,9,1,3] should return 42
    print(max_hopping_score([4,5,2,8,9,1,3]))