Python || O(N) space and time solution || Detailed explanation with comments
class Solution:\n    def maxSumMinProduct(self, nums: List[int]) -> int:\n        # O(N) time and space\n        \n        stack = []\n        res = 0\n        
class Solution:\n    def maxSumMinProduct(self, nums: List[int]) -> int:\n        # O(N) time and space\n        \n        stack = []\n        res = 0\n        n = len(nums)\n        prefix = [0]\n        \n        # prefix sums will help us get sum for any given subarray in O(1) time\n        for i in range(n):\n            prefix.append(prefix[i]+nums[i])\n            \n        # We need to maintain a stack with increasing order of elements\n        # We push a tuple (start, num), start is basically start index of any subarray whose minimum element is num. For every such num being pushed into\n        # stack, we try to find widest subarray, starting from num\'s start and \n        # having num as its minimum element.(Finding widest as we wanna maximize)\n        # the sum.example - [1,2,3,4,2]. Stack- [[0,1,[1,2],[2,3],[3,4]].Now while\n        # pushing 2(at idx 5), we see stack top>2. So basically we can\'t stretch\n        # the subarray having 4 as it\'s min anymore. So we pop that out, and calc\n        # min product for it, which is 4*(prefix[i]-prefix[start]), and update res\n        # Now we need to insert this 2. What value do we keep as it\'s start val?\n        # Since 2 has been the min value since the start of all those elements\n        # that have been popped (the elements 3 and 4), so start idx of a subarray\n        # with this 2 as min would be the start idx of 3, which is 2,so push [2,2]\n        \n        \n        for i in range(n):\n            start = i\n            while stack and stack[-1][1]>nums[i]:\n                start, num = stack.pop()\n                res = max( res, num*(prefix[i]-prefix[start]) )\n            \n            stack.append( (start, nums[i]) )\n        \n        # Elements still remaining in stack will mean they don\'t have any\n        # number to their right which is lesser than them, so we can say\n        # that for an element in stack, longest subarray would be of size\n        # n-start, so we take total of all those elements an multiply with element\n        while stack:\n            start, num = stack.pop()\n            res = max(res, num*(prefix[n]-prefix[start]))\n        \n        return res%(10**9 + 7)\n            \n
['Stack', 'Prefix Sum']