Find the Score of All Prefixes of an Array
We define the conversion array conver of an array arr as follows:
conver[i] = arr[i] + max(arr[0..i]), wheremax(arr[0..i])is the maximum value ofarr[j]over0 <= 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]The prefix scores are 4, 10, 24, 36, and 56 from conversion arrays [4], [4, 6], [4, 6, 14], [4, 6, 14, 12], and [4, 6, 14, 12, 20], respectively.
Example 2
Input
nums = [1,1,2,4,8,16]Output
[2,4,8,16,32,64]The prefix scores are 2, 4, 8, 16, 32, and 64 from conversion arrays [2], [2, 2], [2, 2, 4], [2, 2, 4, 8], [2, 2, 4, 8, 16], and [2, 2, 4, 8, 16, 32], respectively.
Constraints
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^9