class Solution {
public:
long long findMaximumScore(vector<int>& nums) {
}
};
3282. 到达数组末尾的最大得分
给你一个长度为 n 的整数数组 nums 。
你的目标是从下标 0 出发，到达下标 n - 1 处。每次你只能移动到 更大 的下标处。
从下标 i 跳到下标 j 的得分为 (j - i) * nums[i] 。
请你返回你到达最后一个下标处能得到的 最大总得分 。
示例 1：
输入：nums = [1,3,1,5]
输出：7
解释：
一开始跳到下标 1 处，然后跳到最后一个下标处。总得分为 1 * 1 + 2 * 3 = 7 。
示例 2：
输入：nums = [4,3,1,3,2]
输出：16
解释：
直接跳到最后一个下标处。总得分为 4 * 4 = 16 。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 105原站题解
golang 解法, 执行用时: 180 ms, 内存消耗: 8.5 MB, 提交时间: 2024-09-19 09:57:32
func findMaximumScore(nums []int) (ans int64) {
mx := 0
for _, x := range nums[:len(nums)-1] {
mx = max(mx, x)
ans += int64(mx)
}
return
}
cpp 解法, 执行用时: 223 ms, 内存消耗: 167.5 MB, 提交时间: 2024-09-19 09:57:19
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;
}
};
java 解法, 执行用时: 13 ms, 内存消耗: 61.9 MB, 提交时间: 2024-09-19 09:57:05
class Solution {
public long findMaximumScore(List<Integer> nums) {
long ans = 0;
int mx = 0;
for (int i = 0; i < nums.size() - 1; i++) {
mx = Math.max(mx, nums.get(i));
ans += mx;
}
return ans;
}
// array
public long findMaximumScore2(List<Integer> nums) {
Object[] a = nums.toArray(); // 转成数组效率更高
long ans = 0;
int mx = 0;
for (int i = 0; i < a.length - 1; i++) {
mx = Math.max(mx, (int) a[i]);
ans += mx;
}
return ans;
}
}
python3 解法, 执行用时: 280 ms, 内存消耗: 30.1 MB, 提交时间: 2024-09-19 09:56:30
# 贪心
class Solution:
def findMaximumScore(self, nums: List[int]) -> int:
ans = mx = 0
for x in nums[:-1]: # 也可以先 pop 掉最后一个数
mx = max(mx, x)
ans += mx
return ans
# 一行写法，from itertools import accumulate
# return sum(accumulate(nums[:-1], max))