2640-一个数组所有前缀的分数

定义一个数组 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 <= 105
• 1 <= nums[i] <= 109

本题视频讲解

见【双周赛 102】 第二题。

思路

一边遍历，一边计算前缀最大值 mx，以及前缀的得分之和 s。

[sol1-Python3]

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

[sol1-Go]

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 }

复杂度分析

• 时间复杂度：O(n)，其中 n 为 nums 的长度。
• 空间复杂度：O(1)。返回值不计入，仅用到若干额外变量。