Mid/Senior
Maximum Array Hopping Score I
You are given an array nums of n positive integers.
You start at index 0 and want to reach index n - 1. From an index i, you may hop to any index j such that i < j. The score gained from hopping from i to j is (j - i) * nums[j].
Return the maximum total score you can achieve by choosing a sequence of hops that starts at index 0 and ends at index n - 1.
Example 1
Input
nums = [1,5,8]Output
16The best choice is to hop directly from index 0 to index 2, gaining (2 - 0) * 8 = 16 points.
Example 2
Input
nums = [4,5,2,8,9,1,3]Output
42One optimal sequence is to hop from index 0 to index 4 for 36 points, then from index 4 to index 6 for 6 points, totaling 42.
Constraints
- 2 <= nums.length <= 10^3
- 1 <= nums[i] <= 10^5