3282. Reach End of Array With Max Score
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 <= 105
1 <= nums[i] <= 105
Solutions
Solution 1: Greedy
Suppose we jump from index $i$ to index $j$, then the score is $(j - i) \times \text{nums}[i]$. This is equivalent to taking $j - i$ steps, and each step earns a score of $\text{nums}[i]$. Then we continue to jump from $j$ to the next index $k$, and the score is $(k - j) \times \text{nums}[j]$, and so on. If $\text{nums}[i] \gt \text{nums}[j]$, then we should not jump from $i$ to $j$, because the score obtained this way is definitely less than the score obtained by jumping directly from $i$ to $k$. Therefore, each time we should jump to the next index with a value greater than the current index.
We can maintain a variable $mx$ to represent the maximum value of $\text{nums}[i]$ encountered so far. Then we traverse the array from left to right until the second-to-last element, updating $mx$ each time and accumulating the score.
After the traversal, the result is the maximum total score.
The time complexity is $O(n)$, where $n$ is the length of the array $\text{nums}$. The space complexity is $O(1)$.
1 2 3 4 5 6 7 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 |
|