Boosted Prefix Scores

Medium

You are given an array of positive integers values. The **boosted** value of values[j] is values[j] plus the maximum of values[0..j] (the element itself included). The **score** of a prefix is the sum of the boosted values of its elements. Return an array answer of the same length where answer[i] is the score of the prefix values[0..i].

Example 1

values=[3, 1, 4, 2] → [6, 10, 18, 24]

Boosted values: 3 + 3 = 6, 1 + 3 = 4, 4 + 4 = 8, 2 + 4 = 6. Their running sums are [6, 10, 18, 24].

Example 2

values=[5, 5] → [10, 20]

Both elements boost to 10: [10, 20].

Constraints

1 ≤ len(values) ≤ 10⁵
1 ≤ values[i] ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Prefix Sum

Similar problems

Shortest Stretch to the Goal Medium Product of All the Others Medium Studios for Recording Sessions Medium Longest Run with a Given Sum Medium Batch of Segment Adjustments Medium

Input

values=[3, 1, 4, 2]

Expected

[6, 10, 18, 24]

Run checks the first 3 tests in your browser. Submit checks all 90 tests on the server, hidden ones included.