4,5,2,8,9,1,3] Output: 42 Explanation: We can do the hopping `0 -> 4 -> 6` with a score of `(4 - 0) * 9 + (6 - 4) * 3 = 42`.

Constraints:

2 <= nums.length <= 10^3
1 <= nums[i] <= 10^5

Solution

Method 1 – Dynamic Programming (Right-to-Left)

Intuition

We want the maximum score to reach the last index by hopping from earlier indices. For each index, we can hop to any later index, and the score is (j-i)*nums[j]. We can use dynamic programming from right to left, where dp[i] is the best score starting from i. For each i, try all possible j > i and take the best.

Approach

Initialize a dp array of size n, where dp[i] is the max score starting from i.
Set dp[n-1] = 0 (no hops from the last index).
For i from n-2 downto 0:
- For each j in (i+1, n):
  - dp[i] = max(dp[i], (j-i)*nums[j] + dp[j])
The answer is dp[0].

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int maxScore(vector<int>& nums) {\n        int n = nums.size();\n        vector<int> dp(n, 0);\n        for (int i = n-2; i >= 0; --i) {\n            for (int j = i+1; j < n; ++j) {\n                dp[i] = max(dp[i], (j-i)*nums[j] + dp[j]);\n            }\n        }\n        return dp[0];\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light gith

Related Tags