class Solution {
public:
vector<long long> findPrefixScore(vector<int>& nums) {
}
};
6334. 一个数组所有前缀的分数
定义一个数组 arr 的 转换数组 conver 为：
conver[i] = arr[i] + max(arr[0..i])，其中 max(arr[0..i]) 是满足 0 <= j <= i 的所有 arr[j] 中的最大值。定义一个数组 arr 的 分数 为 arr 转换数组中所有元素的和。
给你一个下标从 0 开始长度为 n 的整数数组 nums ，请你返回一个长度为 n 的数组 ans ，其中 ans[i]是前缀 nums[0..i] 的分数。
示例 1：
输入：nums = [2,3,7,5,10] 输出：[4,10,24,36,56] 解释： 对于前缀 [2] ，转换数组为 [4] ，所以分数为 4 。 对于前缀 [2, 3] ，转换数组为 [4, 6] ，所以分数为 10 。 对于前缀 [2, 3, 7] ，转换数组为 [4, 6, 14] ，所以分数为 24 。 对于前缀 [2, 3, 7, 5] ，转换数组为 [4, 6, 14, 12] ，所以分数为 36 。 对于前缀 [2, 3, 7, 5, 10] ，转换数组为 [4, 6, 14, 12, 20] ，所以分数为 56 。
示例 2：
输入：nums = [1,1,2,4,8,16] 输出：[2,4,8,16,32,64] 解释： 对于前缀 [1] ，转换数组为 [2] ，所以分数为 2 。 对于前缀 [1, 1]，转换数组为 [2, 2] ，所以分数为 4 。 对于前缀 [1, 1, 2]，转换数组为 [2, 2, 4] ，所以分数为 8 。 对于前缀 [1, 1, 2, 4]，转换数组为 [2, 2, 4, 8] ，所以分数为 16 。 对于前缀 [1, 1, 2, 4, 8]，转换数组为 [2, 2, 4, 8, 16] ，所以分数为 32 。 对于前缀 [1, 1, 2, 4, 8, 16]，转换数组为 [2, 2, 4, 8, 16, 32] ，所以分数为 64 。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 109原站题解
golang 解法, 执行用时: 108 ms, 内存消耗: 11.3 MB, 提交时间: 2023-04-17 16:45:44
func findPrefixScore(nums []int) []int64 {
ans := make([]int64, len(nums))
mx, s := 0, 0
for i, x := range nums {
mx = max(mx, x) // 前缀最大值
s += x + mx // 累加前缀的得分
ans[i] = int64(s)
}
return ans
}
func max(a, b int) int { if a < b { return b }; return a }
python3 解法, 执行用时: 300 ms, 内存消耗: 38.5 MB, 提交时间: 2023-04-17 16:45:17
class Solution:
def findPrefixScore(self, nums: List[int]) -> List[int]:
ans = []
mx = s = 0
for x in nums:
mx = max(mx, x) # 前缀最大值
s += x + mx # 累加前缀的得分
ans.append(s)
return ans