Python Solution Explained! Monotonically increasing stack O(n)
Code\n\nclass Solution:\n    def maxSumMinProduct(self, nums: List[int]) -> int:\n        mod = 10**9 + 7\n        # create a prefix sum array\n        prefixSu
# Code\n```\nclass Solution:\n    def maxSumMinProduct(self, nums: List[int]) -> int:\n        mod = 10**9 + 7\n        # create a prefix sum array\n        prefixSum = [0]\n\n        for n in nums:\n            prefixSum.append(prefixSum[-1]+n)\n\n        res = -1\n        stack = []\n\n        \'\'\'\n            the idea is to have a monotonically increasing stack\n            whenver an element greater than or equal to the top of the stack is encountered\n                => We push the element onto the stack\n            whenever an element smaller than the top of the stack is encountered.\n            That means we have encountered the an element which terminates the expansion of the current\n            minimum element in consideration throughout the array.\n                => We start popping the elements to the point when stack.top <= current element\n        \'\'\'\n\n        for start, num in enumerate(nums):\n            newStart = start\n            while stack and stack[-1][1] > num:\n                i,val = stack.pop()\n                res = max(res, (prefixSum[start]-prefixSum[i])*val)\n                \'\'\'\n                    Now this new start assignment might be confusing.\n                    Explanation: We were popping stack elements to check the range the new found element\n                    at the index start extends back.\n\n                    In the test case 3,1,5,6,4,2\n                    when we countered 4, we knew the stack had [[1,1],[2,5],[3,6]]\n                    so since stack.top == 6 > 4, we start popping.\n\n                    in the end we are left with [[1,1]]\n                    Now, if we just insert [4,4] i.e the current index of element 4.\n                    We would lose the information that 4 was able to extend back since in the\n                    final for loop(2). we have information about all the stack elements that were able to\n                    span throughout the array.\n\n                    Therefore, to preserve the information of where 4 was able to extend till the back\n                    we give it a new start which corresponds to the index to which it was able to go back.\n                \'\'\'\n                newStart = i\n            stack.append([newStart, num])\n            \n        # loop 2\n        for start, val in stack:\n            res = max(res, (prefixSum[len(nums)]-prefixSum[start])*val)\n\n        return res%mod\n```
['Python3']