maxPrefix and minSuffix | Beats 100% runtime
IntuitionIf an element is greater than the maximum value before it, then it is also greater than all its previous elements. Similarly, if the current element is
# Intuition
If an element is greater than the maximum value before it, then it is also greater than all its previous elements. Similarly, if the current element is smaller than the minimum element after it, then it is also smaller than all the elements that come after it.

# Approach
<!-- Describe your approach to solving the problem. -->
For every index find the max value before it and min value after it using prefix and suffix arrays. Now, check from i=1 till i<n-1,
if(maxPrefix[i]<nums[i] && nums[i]<minSuffix[i])sum+=2;
else if(nums[i-1]<nums[i] && nums[i]<nums[i+1])sum+=1;

# Complexity
- Time complexity:O(N)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:O(N)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    int sumOfBeauties(vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        vector <int> maxPrefix(n,INT_MIN),minSuffix(n,INT_MAX);

        for(int i=1;i<n;i++){
            maxPrefix[i]=max(maxPrefix[i-1],nums[i-1]);
            minSuffix[n-i-1]=min(minSuffix[n-i],nums[n-i]);
        }

        for(int i=1;i<n-1;i++){
            if(maxPrefix[i]<nums[i] && nums[i]<minSuffix[i])sum+=2;
            else if(nums[i-1]<nums[i] && nums[i]<nums[i+1])sum+=1;
        }
        return sum;
    }
};
```
['C++']