# Find the Score of All Prefixes of an Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-score-of-all-prefixes-of-an-array)
Canonical: https://scaleengineer.com/dsa/problems/find-the-score-of-all-prefixes-of-an-array
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
---
## 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 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]
**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:**

**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 <= 105`
* `1 <= nums[i] <= 109`

# Approaches
## Iterative Calculation for Each Prefix
This approach directly follows the problem definition. For each prefix of the input array `nums`, we calculate its corresponding conversion array and then sum up its elements to get the score. We repeat this process for all prefixes from `nums[0..0]` to `nums[0..n-1]`.
**Time:** O(n^2) - The outer loop runs `n` times, and the inner loop runs up to `n` times. The total number of operations is proportional to `1 + 2 + ... + n`, which is `n * (n+1) / 2`, resulting in O(n^2) time complexity. · **Space:** O(n) - We need an array of size `n` to store the answer. The space used by other variables is constant, O(1).
**Pros:** Simple to understand and implement as it directly translates the problem statement into code.
**Cons:** Inefficient due to redundant calculations. For each prefix, it recalculates the conversion values for all its sub-prefixes.; Will result in a "Time Limit Exceeded" (TLE) error for large inputs as specified in the constraints.
### Explanation
This approach directly simulates the process described in the problem. We iterate through each possible prefix of the `nums` array, from `nums[0..0]` up to `nums[0..n-1]`. For each prefix, we calculate its score and store it in the result array `ans`.

To calculate the score for a prefix `nums[0..i]`:
1.  We initialize a `current_score` to zero.
2.  We iterate from `j = 0` to `i`. In this inner loop, we are essentially building the conversion array for the prefix `nums[0..i]` and summing its elements on the fly.
3.  For each `j`, we first find the maximum value in the subarray `nums[0..j]`. This can be done by maintaining a running maximum as we iterate through the prefix.
4.  We then calculate the conversion value `nums[j] + max(nums[0..j])` and add it to our `current_score`.
5.  After the inner loop finishes, `current_score` contains the total score for the prefix `nums[0..i]`, so we set `ans[i] = current_score`.

Because this method involves a nested loop structure where for each `i`, we loop `i+1` times, the overall time complexity is quadratic.

```java
class Solution {
    public long[] findPrefixScore(int[] nums) {
        int n = nums.length;
        long[] ans = new long[n];

        for (int i = 0; i < n; i++) {
            long currentScore = 0;
            int maxInPrefix = 0;
            // Calculate score for prefix nums[0..i]
            for (int j = 0; j <= i; j++) {
                maxInPrefix = Math.max(maxInPrefix, nums[j]);
                long converValue = (long)nums[j] + maxInPrefix;
                currentScore += converValue;
            }
            ans[i] = currentScore;
        }
        return ans;
    }
}
```
### Algorithm
*   Initialize a `long` array `ans` of size `n`.
*   Loop `i` from `0` to `n-1`:
    *   Initialize `current_score = 0L` and `max_in_prefix = 0`.
    *   Loop `j` from `0` to `i` to compute the score for the prefix `nums[0..i]`.
    *   Inside the inner loop, update `max_in_prefix` with the maximum value in `nums[0..j]`.
    *   Calculate the conversion value `(long)nums[j] + max_in_prefix` and add it to `current_score`.
    *   After the inner loop, assign `ans[i] = current_score`.
*   Return `ans`.

## Single Pass with Prefix Score
This is an optimized approach that avoids redundant calculations by using a dynamic programming-like strategy. We observe that the score of a prefix `nums[0..i]` can be derived from the score of the previous prefix `nums[0..i-1]`. Specifically, `score(nums[0..i]) = score(nums[0..i-1]) + conver[i]`, where `conver[i]` is the conversion value for the `i`-th element.
**Time:** O(n) - We iterate through the input array `nums` only once. Each operation inside the loop takes constant time. · **Space:** O(n) - We need an array of size `n` to store the answer. The space used by helper variables is O(1).
**Pros:** Highly efficient, passing within the time limits for the given constraints.; Simple and elegant implementation.
**Cons:** Requires careful handling of potential integer overflows by using `long` data types for scores.
### Explanation
This is an optimized approach that avoids redundant calculations by using a dynamic programming-like strategy. We observe that the score of a prefix `nums[0..i]` can be derived from the score of the previous prefix `nums[0..i-1]`.

Let `ans[i]` be the score of the prefix `nums[0..i]`. By definition:
`ans[i] = sum_{j=0 to i} (nums[j] + max(nums[0..j]))`

We can express `ans[i]` in terms of `ans[i-1]`:
`ans[i] = [sum_{j=0 to i-1} (nums[j] + max(nums[0..j]))] + (nums[i] + max(nums[0..i]))`
This simplifies to the recurrence relation:
`ans[i] = ans[i-1] + (nums[i] + max(nums[0..i]))`

We can iterate through the `nums` array once, keeping track of two things:
1.  The maximum element found so far (`max_so_far`).
2.  The cumulative score of the prefixes (`current_score`), which corresponds to `ans[i-1]` in the current step.

In each step `i`, we update `max_so_far`, calculate the new conversion value `nums[i] + max_so_far`, add it to `current_score`, and store the result in `ans[i]`. Since the score can become very large, we must use a `long` data type for the score and the answer array to prevent integer overflow.

```java
class Solution {
    public long[] findPrefixScore(int[] nums) {
        int n = nums.length;
        long[] ans = new long[n];
        long maxSoFar = 0;
        long currentScore = 0;

        for (int i = 0; i < n; i++) {
            maxSoFar = Math.max(maxSoFar, nums[i]);
            long converValue = (long)nums[i] + maxSoFar;
            currentScore += converValue;
            ans[i] = currentScore;
        }
        return ans;
    }
}
```
### Algorithm
*   Initialize a `long` array `ans` of size `n`.
*   Initialize `max_so_far = 0L` to track the running maximum and `current_score = 0L` to track the running prefix score.
*   Loop `i` from `0` to `n-1`:
    *   Update `max_so_far = max(max_so_far, nums[i])`.
    *   Calculate the conversion value for the current element: `conver_i = (long)nums[i] + max_so_far`.
    *   Update the total score: `current_score += conver_i`.
    *   Store the result: `ans[i] = current_score`.
*   Return `ans`.

# Solutions
### Java

```java
class Solution {
public
  long[] findPrefixScore(int[] nums) {
    int n = nums.length;
    long[] ans = new long[n];
    int mx = 0;
    for (int i = 0; i < n; ++i) {
      mx = Math.max(mx, nums[i]);
      ans[i] = nums[i] + mx + (i == 0 ? 0 : ans[i - 1]);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<long long> findPrefixScore(vector<int> &nums) {
    int n = nums.size();
    vector<long long> ans(n);
    int mx = 0;
    for (int i = 0; i < n; ++i) {
      mx = max(mx, nums[i]);
      ans[i] = nums[i] + mx + (i == 0 ? 0 : ans[i - 1]);
    }
    return ans;
  }
};

```

### Python

```python
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

```