Monostack very similar to LC907
Key point: For each number in the array (index denoted as i), we want to find the the first smaller number on the left (index denoted as l) and on the right (in
Key point: For each number in the array (index denoted as `i`), we want to find the the first smaller number on the left (index denoted as `l`) and on the right (index denoted as `r`), such that we know the answer of which `nums[i]` being the smallest number in the subarray is `nums[i] * sum(nums[l+1:r])`\n\nMono stack is the exactly data structure you want to learn (if you are not familiar with) for this special kind of problem.\n\nThe key idea is to maintain a stack where the elements in the stack is non-decreasing (a trick here is to push index into the stack instead of the real value, but the idea is as such). \n\nAt this point, before we want to push the current index `i` into the stack, we must pop all the index `j` such that `nums[j] > nums[i]` first. After you are popping index `j`, you know that **the smaller index of `j` on the right is `i`, and the smaller index of `j` on the left is stack.top()**. This is exactly what we want. So we know one of the candidate is `nums[j] * sum(nums[stack[-1]+1 : i])`. \n\nAdding an -1 into the stack is another trick for this monostack problem, where we can deal with cases easier when a number have no smaller number on the left.\n\n```python\nclass Solution:\n    def maxSumMinProduct(self, nums: List[int]) -> int:\n        mod = 10**9 + 7\n\t\t\n\t\t# preprocess for a prefix sum\n        presum = [0]\n        n = len(nums)\n        for i in range(n):\n            presum.append(presum[-1] + nums[i])\n        \n\t\tans = 0\n\t\t\n\t\t# monostack\n        stack = [-1]\n        for i in range(n):\n            while len(stack) > 1 and nums[stack[-1]] > nums[i]:\n                j = stack.pop()\n                ans = max(ans, nums[j] * (presum[i] - presum[stack[-1] + 1]))\n            \n            stack.append(i)\n        \n\t\t# for those nums[j] that have no smaller element on the right\n        while len(stack) > 1:\n            j = stack.pop()\n            ans = max(ans, nums[j] * (presum[n] - presum[stack[-1] + 1]))\n        \n        return ans % mod\n```\n\nTime complexity: O(n), because each index is pushed into and popped out from the stack exactly once.\n\nMore monostack problem:\n\n[496. Next Greater Element I](https://leetcode.com/problems/next-greater-element-i/)\n[84. Largest Rectangle in Histogram](https://leetcode.com/problems/largest-rectangle-in-histogram/)\n[907. Sum of Subarray Minimums](https://leetcode.com/problems/sum-of-subarray-minimums/)
[]