Python Monotonic Stack 1 PASS VERY CONSICE
Basic idea is that for every element, if it is minimal element in certain subarry, we want to find left and right border for that subarray. And we can get it by
Basic idea is that for every element, if it is minimal element in certain subarry, we want to find left and right border for that subarray. And we can get it by using monotonic stack.\n\n- For element `a` that bigger than element `d` at stack top. The left border of `a` is the index of element `d` plus 1.\n- For element `b` that smaller than element `c` at stack top. The `c`\'s right border is index of `b` minus 1. And we can also get min-product of `c` as the min-value element in sub-array, by using prefix sum.\n\nFor simplicity, I pre-calculate prefix sum, but you can calculate on the fly for 1 PASS.\n\n`left` is left border.\n```\nclass Solution:\n    def maxSumMinProduct(self, nums: List[int]) -> int:\n        p = [0]\n        for num in nums:\n            p.append(num+p[-1])\n        n = len(nums)\n        ans = 0\n        left = [0 for _ in range(n)]\n        s = []\n        for i in range(n):\n            while s and nums[s[-1]] >= nums[i]:\n                j = s.pop()\n                l, r = left[j], i-1\n                ans = max(ans, (p[r+1]-p[l])*nums[j])\n            if s:\n                left[i] = (s[-1]+1)\n            else:\n                left[i] = 0\n            s.append(i)\n        \n        while s:\n            j = s.pop()\n            l, r = left[j], n-1\n            ans = max(ans, (p[r+1]-p[l])*nums[j])\n        \n        return ans % (10**9+7)\n```\n\nPlease vote if you find helpful.
[]