Reach End of Array With Max Score
MedPrompt
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 <= 1051 <= nums[i] <= 105
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
dparray of sizen, wheredp[i]will store the maximum score to reach indexi. - Initialize
dp[0]to 0, as we start at index 0 with no score. Initialize all otherdpvalues to a very small number. - Iterate with a variable
ifrom 1 ton-1to computedp[i]for each index. - Inside this loop, iterate with a variable
jfrom 0 toi-1. This inner loop considers all possible previous indicesjfrom which we can jump toi. - For each pair
(j, i), calculate the score of jumping fromjtoiand add it to the maximum score to reachj. The formula isdp[j] + (long)(i - j) * nums[j]. - Update
dp[i]with the maximum score found among all possiblej'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.
import java.util.Arrays; class Solution { public long maxScore(int[] nums) { int n = nums.length; if (n <= 1) { return 0; } long[] dp = new long[n]; Arrays.fill(dp, Long.MIN_VALUE); dp[0] = 0; for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { long currentScore = dp[j] + (long)(i - j) * nums[j]; if (currentScore > dp[i]) { dp[i] = currentScore; } } } return dp[n - 1]; }}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.
Solutions
Solution
class Solution {public long findMaximumScore(List<Integer> nums) { long ans = 0; int mx = 0; for (int i = 0; i + 1 < nums.size(); ++i) { mx = Math.max(mx, nums.get(i)); 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.