Find the Score of All Prefixes of an Array — LeetCode 2640 Python Solution

The 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.

Example

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

Python solution

class Solution:
    def findPrefixScore(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [0] * n
        mx = 0
        for i, x in enumerate(nums):
            mx = max(mx, x)
            ans[i] = x + mx + (0 if i == 0 else ans[i - 1])
        return ans

Complexity

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 2640. Find the Score of All Prefixes of an Array is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Prefix Sum.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Related problems