LeetCode Solutions Blog

Reach End of Array With Max Score

Number: 3528

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an array nums of length n, you start at index 0 and need to reach index n-1 by only jumping to indices greater than your current one. The score for a jump from index i to j is defined as (j - i) * nums[i]. The objective is to calculate the maximum possible total score you can accumulate by the time you reach the last index.

Key Insights

The problem is solved using dynamic programming where dp[j] represents the maximum score to reach index j.
Transition: dp[j] = max(for each i < j){ dp[i] + (j - i) * nums[i] }.
Rearranging the formula leads to dp[j] = max(for each i < j){ (dp[i] - i * nums[i]) + j * nums[i] }.
This formulation is similar to a "line query" where each jump corresponds to a line function f(x) = mx + b, with m = nums[i] and b = dp[i] - inums[i].
Using a Li-Chao Tree (or dynamic convex hull trick) efficiently supports adding such lines and querying maximum values in O(log(max_range)) per operation.
The x-values (indices j) are increasing, but the slopes (nums[i]) are arbitrary; hence, the Li-Chao Tree is preferred.

Space and Time Complexity

Time Complexity: O(n * log(max_index)) where max_index is bounded by the number of indices (roughly 1e5).
Space Complexity: O(n) for storing dp values and the lines (nodes) in the Li-Chao Tree.

Solution

We use dynamic programming with a Li-Chao Tree to optimize the state transition. We define a function for each index i as f(x) = nums[i] * x + (dp[i] - i * nums[i]). For a given index j, dp[j] is computed as the maximum value among f(j) over all previously visited indices i (< j). We add these functions to our Li-Chao Tree as we iterate through the array and query the maximum for each j. This method avoids the O(n^2) approach and makes it feasible for large input sizes.

Code Solutions

# Python implementation using Li-Chao Tree

# Define the Line class representing f(x) = m*x + b
class Line:
    def __init__(self, m, b):
        self.m = m  # slope
        self.b = b  # intercept
    
    def get(self, x):
        return self.m * x + self.b

# LiChaoTree implementation for maximum queries
class LiChaoTree:
    def __init__(self, lo, hi):
        self.lo = lo  # lower bound of x
        self.hi = hi  # upper bound of x
        self.line = None  # best line for this segment
        self.left = None
        self.right = None
    
    def add_line(self, new_line):
        lo, hi = self.lo, self.hi
        mid = (lo + hi) // 2
        
        if self.line is None:
            self.line = new_line
            return
        
        # Check which line yields a better value at mid
        if new_line.get(mid) > self.line.get(mid):
            self.line, new_line = new_line, self.line
        
        # Decide in which child segment the new_line may be better
        if lo == hi:
            return
        if new_line.get(lo) > self.line.get(lo):
            if self.left is None:
                self.left = LiChaoTree(lo, mid)
            self.left.add_line(new_line)
        elif new_line.get(hi) > self.line.get(hi):
            if self.right is None:
                self.right = LiChaoTree(mid+1, hi)
            self.right.add_line(new_line)
    
    def query(self, x):
        # Current best value at x
        res = self.line.get(x) if self.line else float('-inf')
        mid = (self.lo + self.hi) // 2
        
        if x <= mid and self.left:
            res = max(res, self.left.query(x))
        elif x > mid and self.right:
            res = max(res, self.right.query(x))
            
        return res

def max_score(nums):
    n = len(nums)
    dp = [0] * n
    # dp[0] is 0 because we start at index 0 without a jump.
    dp[0] = 0
    # Initialize Li-Chao Tree over x in range 0 to n-1.
    tree = LiChaoTree(0, n-1)
    # Add the line corresponding to index 0.
    tree.add_line(Line(nums[0], dp[0] - 0 * nums[0]))
    
    for j in range(1, n):
        # Query the current best value among all lines at x = j.
        dp[j] = tree.query(j)
        # For indices other than the last, add corresponding line for future queries.
        if j < n - 1:
            tree.add_line(Line(nums[j], dp[j] - j * nums[j]))
    
    return dp[n-1]

# Example usage
if __name__ == "__main__":
    print(max_score([1,3,1,5]))  # Expected output: 7
    print(max_score([4,3,1,3,2]))  # Expected output: 16