max rectangular in histogram with prefix sum (python3) O(N)
This problem is very similar to the max rectangular in histogram. 84  https://leetcode.com/problems/largest-rectangle-in-histogram/\nJust replace the "width" wi
This problem is very similar to the max rectangular in histogram. 84  https://leetcode.com/problems/largest-rectangle-in-histogram/\nJust replace the "width" with the subarray sum, which can be obtained by prefix sum in O(1) time.\nAnd take care of the boundary conditions...\n\nNotice that leetcode 84 was "hard". Now this is hard + prefix sum twist, and is only "medium". \nWow, the time has evolved... I am breathless trying to keep up.\n\nMonotonic stack solutions are very hard to grasp because there is a lot "dynamic and delay in time" going on for the stack. \n**The following intuitions may be helpful to recognize when to use it.**\nIt is very useful to get "next bigger item", "next smaller item", "previous bigger item", "previous smaller item" and therefore "window max" and "window min". \nTo get the next **bigger** item, need to use monotonic **decreasing** stack, and the ans is obtained for each item when popping.\nTo get the next **smaller** item, need to use monotonic **increasing** stack, and the ans is obtained for each item when popping.\nTo get the prev **bigger** item, need to use monotonic **decreasing** stack, and the ans is obtained for the enqueueing item at the top of the stack.\nTo get the prev **smaller** item, need to use monotonic **increasing** stack, and the ans is obtained for the enqueueing item at the top of the stack.\n\nTherefore, the left and right boundary for "window max" and "window min" are obtained. \n\nThe above relationship is assuming looping forwards. \nIf looping backwards, the relationship will be "reversed". Sorry, it is quite interesting but easily confused. Correct me if I am wrong...\n\n```\n    def maxSumMinProduct(self, nums: List[int]) -> int:\n\t\t#apply some tricks to simplify the boundary condition checking.\n\t\t#the first -1 makes sure the mono_stack is never empty; the last -1 make sure every element will be popped and computed\n        nums = [-1] + nums + [-1] \n        mono_stack = [0] # mono increasing \n        ans = 0\n        prefix = [0]\n        for n in nums:\n            prefix.append(prefix[-1]+n)\n            \n        for i, n in enumerate(nums[1:],1):\n            while n < nums[mono_stack[-1]]:\n                left = mono_stack.pop()\n                psum = prefix[i] - prefix[mono_stack[-1]+1] # important to +1 here... it is non inclusive boundary\n                height = nums[left]\n                ans = max(ans, psum*height )\n            \n            mono_stack.append(i)\n        \n        return ans%(10**9+7)\n```
[]