Python - Dynamic programming - Explained
\nQuestion: The beauty of nums[i] equals 2, if nums[j] < nums[i] < nums[k], for all 0 <= j < i and for all i < k <= nums.length - 1.\n\nExplanation:\n\nIn simpl
\n***Question***: The beauty of nums[i] equals 2, if nums[j] < nums[i] < nums[k], for all 0 <= j < i and for all i < k <= nums.length - 1.\n\n**Explanation:**\n\nIn simpler terms, for each index from ```1``` till ```n-2```, \n* All the values left of ```i```th index should be less than ```i```th index\'s value.\n* All the values right of ```i```th index should be greater than ```i```th index\'s value.\n\nWe create two dp arrays\n* ```max_dp``` - computation starts from start of array (index 0) - to keep track of maximum value of array from index ```0``` till ```i```th index\n* ```min_dp``` - computation starts from end of array (index n-1) - to keep track of minimum value of array from ```n-1``` index till ```i```th index\n\nWith ```max_dp```, we can find if all values in left side are smaller - ```if max_dp[i] > max_dp[i-1]```\nWith ```min_dp```, we can find if all values in right side are greater - ```if nums[i] < min_dp[i+1]```\n\nThe second condition ```nums[i-1] < nums[i] < nums[i+1]``` is self explanatory\n\n**Code:**\n```\nclass Solution:\n    def sumOfBeauties(self, nums: List[int]) -> int:\n        n = len(nums)\n        max_dp = [0] * n\n        min_dp = [float(inf)] * n\n        max_dp[0] = nums[0]\n        min_dp[-1] = nums[-1]\n        \n        for i in range(1, n):\n            max_dp[i] = max(nums[i], max_dp[i-1])\n            \n        for i in range(n-2, -1, -1):\n            min_dp[i] = min(nums[i], min_dp[i+1])\n        \n        ans = 0\n        for i in range(1, n-1):\n            if max_dp[i-1] < max_dp[i] and nums[i] < min_dp[i+1]:\n                ans += 2\n            elif nums[i-1] < nums[i] < nums[i+1]:\n                ans += 1\n        return ans\n```\n\n**Time and space complexity: O(n)**
['Dynamic Programming', 'Python']