C++ Left and Right
See my latest update in repo LeetCode\n\n## Solution 1.\n\nIntuition: Let left[i] be the greatest value in A[0..i], and right[i] be the smallest value in A[i..(
See my latest update in repo [LeetCode](https://github.com/lzl124631x/LeetCode)\n\n## Solution 1.\n\n**Intuition**: Let `left[i]` be the greatest value in `A[0..i]`, and `right[i]` be the smallest value in `A[i..(N-1)]`. For the first condition, we just need to check if `A[i] > left[i - 1] && A[i] < right[i + 1]`.\n\n**Algorithm**:\n\nWe can precompute the `right` array and then compute `left` on the fly. \n\n```cpp\n// OJ: https://leetcode.com/problems/sum-of-beauty-in-the-array/\n// Author: github.com/lzl124631x\n// Time: O(N)\n// Space: O(N)\nclass Solution {\npublic:\n    int sumOfBeauties(vector<int>& A) {\n        int N = A.size(), left = A[0], ans = 0;\n        vector<int> right(N, A[N - 1]);\n        for (int i = N - 2; i > 0; --i) right[i] = min(right[i + 1], A[i]);\n        for (int i = 1; i < N - 1; ++i) {\n            if (A[i] > left && A[i] < right[i + 1]) ans += 2;\n            else if (A[i] > A[i - 1] && A[i] < A[i + 1]) ans++;\n            left = max(left, A[i]);\n        }\n        return ans;\n    }\n};\n```
[]