We define the conversion array converof an array arras follows:

conver[i] = arr[i] + max(arr[0..i])where max(arr[0..i])is the maximum value of arr[j]over 0 <= j <= i.

(相关资料图)

We also define the score of an array arras the sum of the values of the conversion array of arr.

Given a 0-indexed integer array numsof length n, return an array ansof length nwhere ans[i]is the score of the prefix nums[0..i].

Example 1:

Input: nums = [2,3,7,5,10]

Output: [4,10,24,36,56]

Explanation:

For the prefix [2], the conversion array is [4] 

hence the score is 4 

For the prefix [2, 3], the conversion array is [4, 6] 

hence the score is 10 

For the prefix [2, 3, 7], the conversion array is [4, 6, 14]

hence the score is 24 

For the prefix [2, 3, 7, 5], the conversion array is [4, 6, 14, 12] 

hence the score is 36 

For the prefix [2, 3, 7, 5, 10], the conversion array is [4, 6, 14, 12, 20] 

hence the score is 56

Example 2:

Input: nums = [1,1,2,4,8,16]

Output: [2,4,8,16,32,64]

Explanation: 

For the prefix [1], the conversion array is [2] 

hence the score is 2 

For the prefix [1, 1], the conversion array is [2, 2] 

hence the score is 4 

For the prefix [1, 1, 2], the conversion array is [2, 2, 4] 

hence the score is 8 

For the prefix [1, 1, 2, 4], the conversion array is [2, 2, 4, 8] 

hence the score is 16 

For the prefix [1, 1, 2, 4, 8], the conversion array is [2, 2, 4, 8, 16] 

hence the score is 32 

For the prefix [1, 1, 2, 4, 8, 16], the conversion array is [2, 2, 4, 8, 16, 32] 

hence the score is 64

先是计算convert数组，就是arr[i]+max((0-i)of arr[])

然后pre_sum；

最后返回即可，

不是难的题目；

可能提交的人少，所以数据看着还可以的。

Constraints:

1 <= nums.length <= 105

1 <= nums[i] <= 109

Accepted

12,032

Submissions

17,385

Runtime: 3 ms, faster than 100.00% of Java online submissions for Find the Score of All Prefixes of an Array.

Memory Usage: 72.5 MB, less than 100.00% of Java online submissions for Find the Score of All Prefixes of an Array.

关键词：