[Java/Python 3] O(n) code: running max/min from left and right, w/ brief explanation and analysis.
Compute running max from left and running min from left in order to check if nums[i] < nums[j] < nums[k] , for all 0 <= j < i and for all i < k <= nums.length -
1. Compute running max from left and running min from left in order to check if `nums[i] < nums[j] < nums[k]` , for all `0 <= j < i` and for all `i < k <= nums.length - 1`;\n2. Traverse the input array `nums` to get the beauty value.\n\n```java\n    public int sumOfBeauties(int[] nums) {\n        int sum = 0, n = nums.length;\n        int[] mi = new int[n + 1], mx = new int[n + 1];\n        mi[n] = Integer.MAX_VALUE;\n        for (int i = 0, j = n - 1; i < n; ++i, --j) {\n            mx[i + 1] = Math.max(nums[i], mx[i]);\n            mi[j] = Math.min(nums[j], mi[j + 1]);\n        }\n        for (int i = 1; i < nums.length - 1; ++i) {\n            if (mx[i] < nums[i] && nums[i] < mi[i + 1]) {\n                sum += 2;\n            }else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {\n                ++sum;\n            }\n        }\n        return sum;\n    }\n```\n\n```python\n    def sumOfBeauties(self, nums: List[int]) -> int:\n        n, sm = len(nums), 0\n        mi, mx = [0] * n + [math.inf], [0] * (n + 1)\n        for i, num in enumerate(nums):\n            mx[i + 1] = max(num, mx[i])\n            mi[~i - 1] = min(nums[~i], mi[~i])\n        for i in range(1, len(nums) - 1):\n            if mx[i] < nums[i] < mi[i + 1]:\n                sm += 2\n            elif nums[i - 1] < nums[i] < nums[i + 1]:\n                sm += 1\n        return sm \n```\n\n----\n\n`mx` array is not necessary, and a running max value suffices. - credit to **@lattu**.\n\n```java\n    public int sumOfBeauties(int[] nums) {\n        int sum = 0, n = nums.length;\n        int[] mi = new int[n + 1];\n        mi[n] = Integer.MAX_VALUE;\n        for (int i = n - 1; i >= 0; --i) {\n            mi[i] = Math.min(nums[i], mi[i + 1]);\n        }\n        for (int i = 1, mx = nums[0]; i < nums.length - 1; ++i) {\n            if (mx < nums[i] && nums[i] < mi[i + 1]) {\n                sum += 2;\n            }else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {\n                ++sum;\n            }\n            mx = Math.max(mx, nums[i]);\n        }\n        return sum;\n    }\n```\n```python\n    def sumOfBeauties(self, nums: List[int]) -> int:\n        mi, mx, sm = [math.inf], nums[0], 0\n        for num in reversed(nums):\n            mi.append(min(mi[-1], num))\n        mi.reverse()\n        for i in range(1, len(nums) - 1):\n            if mx < nums[i] < mi[i + 1]:\n                sm += 2\n            elif nums[i - 1] < nums[i] < nums[i + 1]:\n                sm += 1\n            mx = max(mx, nums[i])    \n        return sm \n```\n**Analysis:**\n\nTime & space: `O(n)`, where `n = nums.length`.
[]