Reach End of Array With Max Score

MEDIUM

Description

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

Checkout 2 different approaches to solve Reach End of Array With Max Score. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Dynamic Programming

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].

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 Analysis

Time Complexity: 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 Complexity: O(n) - We use a DP array of size `n` to store the maximum scores for each index.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Reach End of Array With Max Score. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Reach End of Array With Max Score

Patterns:

Greedy

Data Structures:

Array