题目描述
定义一个数组 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]
的分数。
样例
输入: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。
输入: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^5
1 <= nums[i] <= 10^9
算法
(前缀遍历) $O(n)$
- 第一次遍历求出
conver
数组每个元素的值,遍历过程中记录下当前的最大值。 - 第二次遍历求
conver
的前缀和数组,得到答案。
时间复杂度
- 遍历数组两次,故时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储答案。
C++ 代码
#define LL long long
class Solution {
public:
vector<LL> findPrefixScore(vector<int>& nums) {
const int n = nums.size();
int ma = 0;
for (int i = 0; i < n; i++) {
ma = max(ma, nums[i]);
nums[i] += ma;
}
vector<LL> ans(n);
ans[0] = nums[0];
for (int i = 1; i < n; i++)
ans[i] = ans[i - 1] + nums[i];
return ans;
}
};