Solution using Prefix and Suffix Arrays (DP)
IntuitionThe problem asks us to compute a "beauty" score for each element in the array (except the first and last). The score depends on how nums[i] compares to
# Intuition  
The problem asks us to compute a "beauty" score for each element in the array (except the first and last). The score depends on how `nums[i]` compares to elements before and after it.  
- My first thought was that to efficiently determine if `nums[i]` is greater than all elements to its left and less than all elements to its right, we could **precompute** prefix maximums and suffix minimums.  
- This helps avoid nested loops and reduces the time complexity to linear.

---

# Approach  
1. **Prefix Maximum Array**:  
   - For each index `i`, store the maximum of all elements from `nums[0]` to `nums[i]`.
   - This helps check if `nums[i]` is greater than all previous values.

2. **Suffix Minimum Array**:  
   - For each index `i`, store the minimum of all elements from `nums[i]` to the end.
   - This helps check if `nums[i]` is less than all following values.

3. **Iterate from 1 to n-2**:
   - If `nums[i]` is strictly greater than `prefix[i-1]` and strictly less than `suffix[i+1]`, add 2 to the score.
   - Else if `nums[i-1] < nums[i] < nums[i+1]`, add 1.
   - Else, add 0 (implicitly by doing nothing).

This approach ensures we check the required conditions efficiently for each relevant index.

---

# Complexity  
- **Time complexity:**  
  $$O(n)$$  
  One pass for prefix, one for suffix, and one for final iteration → total linear time.

- **Space complexity:**  
  $$O(n)$$  
  For storing the prefix and suffix arrays. Can be optimized to $$O(1)$$ with in-place comparisons, but this version prioritizes clarity.

---

# Code  
```cpp
class Solution {
public:
    int sumOfBeauties(vector<int>& nums) {
        int n = nums.size();

        vector<int> prefix(n, 0);
        prefix[0] = nums[0];
        for(int i = 1; i < n; i++){
            prefix[i] = max(prefix[i - 1], nums[i]);
        }

        vector<int> suffix(n, 0);
        suffix[n - 1] = nums[n - 1];
        for(int i = n - 2; i >= 0; i--){
            suffix[i] = min(suffix[i + 1], nums[i]);
        }

        int answer = 0;
        for(int i = 1; i < n - 1; i++){
            if(nums[i] > prefix[i - 1] && nums[i] < suffix[i + 1]){
                answer += 2;
            } else if(nums[i - 1] < nums[i] && nums[i] < nums[i + 1]){
                answer++;
            }
        }

        return answer;
    }
};
```
['Array', 'Dynamic Programming', 'C++']