题目描述

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

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

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

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

样例

输入：nums = [1,3,1,5]

输出：7

解释：

一开始跳到下标 1 处，然后跳到最后一个下标处。总得分为 1 * 1 + 2 * 3 = 7。

输入：nums = [4,3,1,3,2]

输出：16

解释：

直接跳到最后一个下标处。总得分为 4 * 4 = 16。

限制

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

算法

(贪心) $O(n)$

1. 注意到，当选择了某个位置 $p$ 时，如果后续选择的位置上的数字都不比位置 $p$ 的数字大时，不如一直都选择位置 $p$ 作为上一个转移点。
2. 根据这个发现，可以从初始位置开始遍历，如果遇到数字比上一个位置的数字大时，则从上一个位置跳到当前位置。

时间复杂度

• 遍历数组一次，故时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

#define LL long long

class Solution {
public:
    LL findMaximumScore(vector<int>& nums) {
        const int n = nums.size();

        int p = 0;
        LL ans = 0;
        for (int i = 1; i < n; i++) {
            if (nums[i] <= nums[p])
                continue;

            ans += (LL)(i - p) * nums[p];
            p = i;
        }

        ans += (LL)(n - 1 - p) * nums[p];

        return ans;
    }
};