Reach End of Array With Max Score

Med

#2913Time: O(n^2) - There are two nested loops. The outer loop runs `n` times, and the inner loop runs up to `n` times, leading to a quadratic time complexity.Space: O(n) - We use a DP array of size `n` to store the maximum scores for each index.

Patterns

Greedy

Data structures

Array

Prompt

You are given an integer array nums of length n.

Your goal is to start at index 0 and reach index n - 1. You can only jump to indices greater than your current index.

The score for a jump from index i to index j is calculated as (j - i) * nums[i].

Return the maximum possible total score by the time you reach the last index.

Example 1:

Input: nums = [1,3,1,5]

Output: 7

Explanation:

First, jump to index 1 and then jump to the last index. The final score is 1 * 1 + 2 * 3 = 7.

Example 2:

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

Output: 16

Explanation:

Jump directly to the last index. The final score is 4 * 4 = 16.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses dynamic programming to solve the problem. We define dp[i] as the maximum score to reach index i. The base case is dp[0] = 0, as we start at index 0. To compute dp[i], we consider all possible previous indices j (where 0 <= j < i) from which we could have jumped to i. The total score for a path that ends with a jump from j to i is the maximum score to reach j (dp[j]) plus the score of the jump itself, which is (i - j) * nums[j]. We take the maximum over all possible j to find dp[i]. This leads to a straightforward nested loop implementation.

Algorithm

Create a dp array of size n, where dp[i] will store the maximum score to reach index i.
Initialize dp[0] to 0, as we start at index 0 with no score. Initialize all other dp values to a very small number.
Iterate with a variable i from 1 to n-1 to compute dp[i] for each index.
Inside this loop, iterate with a variable j from 0 to i-1. This inner loop considers all possible previous indices j from which we can jump to i.
For each pair (j, i), calculate the score of jumping from j to i and add it to the maximum score to reach j. The formula is dp[j] + (long)(i - j) * nums[j].
Update dp[i] with the maximum score found among all possible j's: dp[i] = max(dp[i], dp[j] + (long)(i - j) * nums[j]).
After the loops complete, dp[n-1] will hold the maximum score to reach the final index.
Return dp[n-1].

Walkthrough

The recurrence relation for this dynamic programming approach is:

dp[i] = max(dp[j] + (i - j) * nums[j]) for all 0 <= j < i.

We can implement this by creating an array dp of size n. We initialize dp[0] = 0 and then iterate from i = 1 to n-1. For each i, we have an inner loop that iterates from j = 0 to i-1, calculating the potential score from each j and updating dp[i] if a better path is found. We use long for score calculation to avoid overflow, as the scores can become large.

1import java.util.Arrays;2 3class Solution {4    public long maxScore(int[] nums) {5        int n = nums.length;6        if (n <= 1) {7            return 0;8        }9 10        long[] dp = new long[n];11        Arrays.fill(dp, Long.MIN_VALUE);12        dp[0] = 0;13 14        for (int i = 1; i < n; i++) {15            for (int j = 0; j < i; j++) {16                long currentScore = dp[j] + (long)(i - j) * nums[j];17                if (currentScore > dp[i]) {18                    dp[i] = currentScore;19                }20            }21        }22 23        return dp[n - 1];24    }25}

Complexity

Time

O(n^2) - There are two nested loops. The outer loop runs `n` times, and the inner loop runs up to `n` times, leading to a quadratic time complexity.

Space

O(n) - We use a DP array of size `n` to store the maximum scores for each index.

Trade-offs

Pros

Simple to understand and implement.
Correctly solves the problem for smaller input sizes.

Cons

The time complexity of O(n^2) is too slow for the given constraints (n <= 10^5) and will result in a Time Limit Exceeded (TLE) error on most platforms.

The O(n^2) DP approach can be optimized by re-examining the recurrence relation. By rearranging the terms, we can see that calculating dp[i] is equivalent to finding the maximum value among a set of linear functions. Specifically, for each previous index j, we can define a line y = nums[j] * x + (dp[j] - j * nums[j]). Then, dp[i] is the maximum y value obtained by evaluating all lines L_j (for j < i) at x = i.

This problem of maintaining a set of lines and querying for the maximum value at a point is known as the Convex Hull Trick. Since we are adding lines whose slopes (nums[j]) are not in a specific order, we need a dynamic version of this technique. A Li Chao Tree is a data structure that excels at this, allowing both line insertions and point queries in logarithmic time.

Algorithm

First, observe the DP recurrence: dp[i] = max_{0 <= j < i} (dp[j] + (i - j) * nums[j]).
Rearrange the expression inside the max: dp[i] = max_{0 <= j < i} (nums[j] * i + (dp[j] - j * nums[j])).
This can be viewed as a computational geometry problem. For each j, we have a line L_j(x) = m_j * x + c_j, where the slope m_j = nums[j], the y-intercept c_j = dp[j] - j * nums[j], and we are querying for the maximum line value at x = i.
This is a classic Convex Hull Trick (CHT) problem. Since the slopes m_j = nums[j] are not added in monotonic order, and we need to perform point queries, a dynamic CHT data structure is required.
A Li Chao Tree is a suitable data structure for this. It's a segment tree built over the coordinate space (here, the indices 0 to n-1) that can efficiently handle adding lines and querying for the maximum value at a specific point.
The overall algorithm is:
1. Initialize dp[0] = 0.
2. Create a Li Chao Tree for the coordinate range [0, n-1].
3. Create the first line L_0 with m = nums[0] and c = 0, and add it to the tree.
4. Iterate i from 1 to n-1: a. Query the Li Chao Tree at x = i to find the maximum score, which is dp[i]. b. Create a new line L_i with m = nums[i] and c = dp[i] - (long)i * nums[i]. c. Add this new line L_i to the Li Chao Tree.
5. Return dp[n-1].

Walkthrough

A Li Chao Tree is a segment tree where each node stores a single line that represents the upper envelope for some part of that node's range. When we add a new line, it's propagated down the tree, potentially replacing the line in some nodes if it's better. A query for a point x involves traversing from the root to the leaf corresponding to x, taking the maximum of the lines stored in the nodes along this path.

Both adding a line and querying for a point take O(log C) time, where C is the size of the coordinate space. In our case, C = n.

Here is the high-level structure of the solution using a Li Chao Tree:

1class Solution {2    // Represents a line y = mx + c3    static class Line {4        long m, c;5        public Line(long m, long c) {6            this.m = m;7            this.c = c;8        }9        public long eval(long x) {10            return m * x + c;11        }12    }13 14    // Placeholder for Li Chao Tree implementation15    static class LiChaoTree {16        // ... implementation details ...17        // public void addLine(Line line) { ... }18        // public long query(int x) { ... }19    }20 21    public long maxScore(int[] nums) {22        int n = nums.length;23        if (n <= 1) {24            return 0;25        }26 27        // The actual Li Chao Tree would be initialized here.28        // For demonstration, we'll just show the logic.29        // LiChaoTree tree = new LiChaoTree(0, n - 1);30 31        long[] dp = new long[n];32        dp[0] = 0;33 34        Line firstLine = new Line(nums[0], 0);35        // tree.addLine(firstLine);36 37        for (int i = 1; i < n; i++) {38            // dp[i] = tree.query(i);39            // The following is a placeholder for the query result40            // In a real scenario, you would compute this with the tree.41            // For now, we re-calculate it naively to show the logic flow.42            long maxVal = Long.MIN_VALUE;43            for (int j = 0; j < i; j++) {44                long val = (long)nums[j] * i + (dp[j] - (long)j * nums[j]);45                maxVal = Math.max(maxVal, val);46            }47            dp[i] = maxVal;48 49            Line newLine = new Line(nums[i], dp[i] - (long)i * nums[i]);50            // tree.addLine(newLine);51        }52 53        return dp[n - 1];54    }55}

Note: A full Li Chao Tree implementation is quite involved and has been omitted for brevity. The key is understanding its role in optimizing the DP state transitions.

Complexity

Time

O(n log n) - The main loop runs `n` times. Inside the loop, both the query and add operations on the Li Chao Tree take `O(log n)` time.

Space

O(n) - We use a `dp` array of size `n`. The Li Chao Tree also requires `O(n)` space for its nodes.

Trade-offs

Pros

Highly efficient, with a time complexity that passes the given constraints.
It's a general technique applicable to a range of DP optimization problems.

Cons

The implementation of a Li Chao Tree is complex and non-trivial.
Requires understanding of computational geometry concepts (Convex Hull Trick).

Solutions

Solution

1class Solution {2public3  long findMaximumScore(List<Integer> nums) {4    long ans = 0;5    int mx = 0;6    for (int i = 0; i + 1 < nums.size(); ++i) {7      mx = Math.max(mx, nums.get(i));8      ans += mx;9    }10    return ans;11  }12}

1class Solution {2public:3  long long findMaximumScore(vector<int> &nums) {4    long long ans = 0;5    int mx = 0;6    for (int i = 0; i + 1 < nums.size(); ++i) {7      mx = max(mx, nums[i]);8      ans += mx;9    }10    return ans;11  }12};

1class Solution:2    def findMaximumScore(self, nums: List[int]) -> int: ans = mx = 0 for x in nums[: - 1]: mx = max(mx, x) ans += mx return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem