3282. 到达数组末尾的最大得分

English Version

题目描述

给你一个长度为 n 的整数数组 nums 。

你的目标是从下标 0 出发，到达下标 n - 1 处。每次你只能移动到 更大 的下标处。

从下标 i 跳到下标 j 的得分为 (j - i) * nums[i] 。

请你返回你到达最后一个下标处能得到的 最大总得分 。

 

示例 1：

示例 2：

 

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

解法

方法一：贪心

假设我们从下标 $i$，跳到下标 $j$，那么得分为 $(j - i) \times \text{nums}[i]$。这相当于我们走了 $j - i$ 步，每一步都得到了 $\text{nums}[i]$ 的得分。然后我们从 $j$ 继续跳到下一个下标 $k$，得分为 $(k - j) \times \text{nums}[j]$，以此类推。如果 $nums[i] \gt nums[j]$，那么我们就不应该从 $i$ 跳到 $j$，因为这样得到的得分一定比从 $i$ 直接跳到 $k$ 得到的得分要少。因此，我们每一次应该跳到下一个比当前下标对应的值更大的下标。

我们可以维护一个变量 $mx$，表示当前为止，我们遇到的最大的 $\text{nums}[i]$ 的值。然后我们从左到右遍历数组，直到倒数第二个元素，每次更新 $mx$，并且累加得分。

遍历结束后，我们得到的就是最大的总得分。

时间复杂度 $O(n)$，其中 $n$ 为数组 $\text{nums}$ 的长度。空间复杂度 $O(1)$。

Python3

class Solution:
    def findMaximumScore(self, nums: List[int]) -> int:
        ans = mx = 0
        for x in nums[:-1]:
            mx = max(mx, x)
            ans += mx
        return ans

Java

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

C++

class Solution {
public:
    long long findMaximumScore(vector<int>& nums) {
        long long ans = 0;
        int mx = 0;
        for (int i = 0; i + 1 < nums.size(); ++i) {
            mx = max(mx, nums[i]);
            ans += mx;
        }
        return ans;
    }
};

Go

func findMaximumScore(nums []int) (ans int64) {
	mx := 0
	for _, x := range nums[:len(nums)-1] {
		mx = max(mx, x)
		ans += int64(mx)
	}
	return
}

TypeScript

function findMaximumScore(nums: number[]): number {
    let [ans, mx]: [number, number] = [0, 0];
    for (const x of nums.slice(0, -1)) {
        mx = Math.max(mx, x);
        ans += mx;
    }
    return ans;
}