Reach End of Array With Max Score

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.

• 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];
    }
}