Find the Score of All Prefixes of an Array - Solution & Explanation

Problem Overview: You receive an integer array nums. For every prefix nums[0..i], compute a converted value where each element becomes nums[i] + max(nums[0..i]). The score of a prefix is the cumulative sum of these converted values up to that index. The task is to return the score for every prefix.

Approach 1: Naive Approach Using Loop (Time: O(n²), Space: O(1))

For each index i, scan the prefix nums[0..i] to find the maximum value. Use that maximum to compute the converted value nums[i] + maxPrefix. Maintain a running total to build the score array. This approach repeatedly recomputes the prefix maximum, which costs O(i) work per step and leads to O(n²) total time.

The logic is straightforward and useful for understanding the definition of the conversion array. However, repeated maximum scans make it inefficient for large inputs. This version mainly helps validate correctness before optimizing.

Approach 2: Optimized Prefix Sum with Running Max (Time: O(n), Space: O(1) extra)

The key observation: the prefix maximum does not need to be recomputed each time. Maintain a variable runningMax that stores the largest value seen so far while iterating once through the array. At index i, update runningMax = max(runningMax, nums[i]). The converted value becomes nums[i] + runningMax.

Next, accumulate scores using a running prefix sum. Maintain currentScore and add the converted value at each step. Append that value to the result array. This single pass simultaneously maintains the prefix maximum and the cumulative score, reducing the total work to O(n).

This approach combines two classic techniques: tracking a running maximum from array traversal and maintaining cumulative totals with a prefix sum. Because every element is processed exactly once, it scales efficiently even for large inputs.

Recommended for interviews: The optimized running-max approach is what interviewers expect. It shows you recognize redundant work in repeated prefix scans and replace it with a maintained state variable. Mentioning the naive O(n²) idea first demonstrates understanding of the problem definition, but implementing the O(n) solution proves you can optimize using prefix sums and incremental computation.