一个数组所有前缀的分数

难度: Medium

定义一个数组 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 <= 10⁵
1 <= nums[i] <= 10⁹

Submission

运行时间: 162 ms

内存: 39.4 MB

class Solution:
    def findPrefixScore(self, nums: List[int]) -> List[int]:
        ans = []
        score = 0
        max_value = -math.inf
        for num in nums:
            if num > max_value:
                max_value = num
            score += num + max_value
            ans.append(score)
        return ans

Explain

此题解的核心思路是在遍历数组 `nums` 的过程中，动态地维护当前为止的最大值 `max_value` 和前缀分数 `score`。对于数组 `nums` 的每个元素 `num`，更新 `max_value` 为 `max(max_value, num)`，然后将 `num + max_value` 添加到 `score` 中。最后将当前的 `score` 添加到结果数组 `ans` 中。这样，每遍历一个元素，就能计算出到当前元素为止的前缀分数，最后返回结果数组。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def findPrefixScore(self, nums: List[int]) -> List[int]:
        ans = []  # 结果数组
        score = 0  # 初始化分数为0
        max_value = -math.inf  # 初始化最大值为负无穷
        for num in nums:
            if num > max_value:  # 更新最大值
                max_value = num
            score += num + max_value  # 计算当前元素的转换值并更新分数
            ans.append(score)  # 将当前分数添加到结果数组
        return ans  # 返回结果数组

Explore

是的，这种逻辑确保了`max_value`总是当前遍历过的元素中的最大值。因为每次遍历到一个新元素`num`时，通过`max(max_value, num)`比较，不管`num`是大于还是小于`max_value`，`max_value`都会更新为这两者中的最大值，从而保持`max_value`总是为迄今为止遇到的最大元素。

当数组`nums`为空时，由于没有元素可以遍历，结果数组`ans`应该也为空。这种情况下应该在算法开始处加入一个检查：如果`nums`为空，则直接返回空数组`[]`。这是必要的，因为在空数组上进行迭代或尝试访问元素将导致错误或不合逻辑的行为。

理论上，`score`的值有可能为负。这主要发生在数组`nums`中的元素都或大部分是负数，且`max_value`也为负数的情况下。例如，如果数组中的元素是[-5, -3, -10]，`max_value`和`score`都将从负值开始，并且可能在某些情况下保持为负。尤其是在最初几次迭代的时候，如果`max_value`和`num`都是较大的负数，那么`score += num + max_value`的结果可能仍然为负。

在每次迭代中即时更新分数允许算法同时计算并存储所有前缀的分数，这样可以直接得到每个前缀对应的分数结果。如果选择在所有迭代完成后一次性计算，我们将需要额外的逻辑和可能的数据结构来存储每个前缀的状态，这样做会增加算法的复杂性和可能的资源消耗。即时更新使得算法更直接、更高效，并且可以轻松地跟踪每步的结果。