Problem

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 arrayans of lengthn whereans[i]is the score of the prefix nums[0..i].

Examples

Example 1

1
2
3
4
5
6
7
8

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

1
2
3
4
5
6
7
8
9

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

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9

Solution

Method 1 – Prefix Maximum and Prefix Sum

Intuition

For each prefix nums[0..i], the conversion array is defined as conver[j] = nums[j] + max(nums[0..j]). The score of the prefix is the sum of conver[0..i]. We can maintain the running maximum and running sum to compute the answer efficiently.

Approach

  1. Initialize max_so_far = 0, sum_so_far = 0, ans = [].
  2. For each index i from 0 to n-1:
    • Update max_so_far = max(max_so_far, nums[i]).
    • Add nums[i] + max_so_far to sum_so_far.
    • Append sum_so_far to ans.
  3. Return ans.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    vector<long long> findPrefixScore(vector<int>& nums) {
        int n = nums.size();
        vector<long long> ans;
        int mx = 0;
        long long sum = 0;
        for (int i = 0; i < n; ++i) {
            mx = max(mx, nums[i]);
            sum += nums[i] + mx;
            ans.push_back(sum);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func findPrefixScore(nums []int) []int64 {
    n := len(nums)
    ans := make([]int64, n)
    mx := 0
    sum := int64(0)
    for i := 0; i < n; i++ {
        if nums[i] > mx {
            mx = nums[i]
        }
        sum += int64(nums[i] + mx)
        ans[i] = sum
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public long[] findPrefixScore(int[] nums) {
        int n = nums.length;
        long[] ans = new long[n];
        int mx = 0;
        long sum = 0;
        for (int i = 0; i < n; ++i) {
            mx = Math.max(mx, nums[i]);
            sum += nums[i] + mx;
            ans[i] = sum;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun findPrefixScore(nums: IntArray): LongArray {
        val n = nums.size
        val ans = LongArray(n)
        var mx = 0
        var sum = 0L
        for (i in 0 until n) {
            mx = maxOf(mx, nums[i])
            sum += nums[i] + mx
            ans[i] = sum
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def findPrefixScore(self, nums: list[int]) -> list[int]:
        ans = []
        mx = 0
        s = 0
        for x in nums:
            mx = max(mx, x)
            s += x + mx
            ans.append(s)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
    pub fn find_prefix_score(nums: Vec<i32>) -> Vec<i64> {
        let n = nums.len();
        let mut ans = Vec::with_capacity(n);
        let mut mx = 0;
        let mut sum = 0i64;
        for &x in &nums {
            mx = mx.max(x);
            sum += (x + mx) as i64;
            ans.push(sum);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    findPrefixScore(nums: number[]): number[] {
        const n = nums.length;
        const ans: number[] = [];
        let mx = 0, sum = 0;
        for (let i = 0; i < n; ++i) {
            mx = Math.max(mx, nums[i]);
            sum += nums[i] + mx;
            ans.push(sum);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — One pass through the array.
  • 🧺 Space complexity: O(n) — For the output array.