We define the?conversion array?conver?of an array?arr?as 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?arr?as the sum of the values of the conversion array of?arr.

Given a?0-indexed?integer array?nums?of length?n, return?an array?ans?of length?n?where?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數(shù)組，就是arr[i]+max((0-i)of arr[])

然后pre_sum；

最后返回即可，

不是難的題目；

可能提交的人少，所以數(shù)據(jù)看著還可以的。

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.