Step by step Intuition for DP Solution
Intuition\nTo find the maximum min-product, we want to check all min products. This means for each element in nums, we want to find the min product it is associ
# Intuition\nTo find the maximum min-product, we want to check all min products. This means for each element in nums, we want to find the min product it is associated with assuming that element is the minimum.\n\nNow finding and summing up the longest subarray in which each element is the minimum is very costly. **Prefix sums** seem like a good idea, since if we could track a running sum, we wouldn\'t have to recompute subarray sums multiple times. But how can we find the right prefix sum on both sides of the minimum?\n\nOne intuitive idea is that if the elements were sorted, it would be much easier to reason about the subarrays. However, since order must be preserved, this means we can\'t sort the array. Instead, we can maintain an increasing **monotonic stack**. This way, we have structure we can work with. More specifically, if we maintain a monotonic stack, we know that for any element x, any element to the left x must be less than it.\n\n# Approach\nWe will use the strategy outlined above, tracking a stack containing (value, prefix sum) pairs and the current maximum min product.\n\nWe then for loop over nums. At each item, we pop the stack while the top of the stack is greater than the current it, adding the top stack\'s value and its prefix sum to a running total that is initialized at 0. During each pop, we update our answer if (new total * the item we just popped) is the new largest min product. All the while, we track the new prefix sum by adding each stack element greater than or equal to our current item to a running total **psum**.\n\nAfter all elements greater than the current item have been removed, we append the new item with an additional field **psum**.\n\nThen at the end we pop everything from the stack using the same process in order to clean up the remaining elements.\n\n# Complexity\n- Time complexity:\nO(n), since everything can only be added to and removed from the stack once each.\n\n- Space complexity:\nO(n), since the stack only holds one pair of data for every entry in nums.\n\n# Code\n```\nclass Solution:\n    def maxSumMinProduct(self, nums: List[int]) -> int:\n        modulo = 10**9+7\n        stack = []\n        ans = 0 \n\n        for i in nums:\n            psum = 0\n            if stack and stack[len(stack)-1][0] > i:\n                total = 0\n                while stack and stack[len(stack)-1][0] >= i:\n                    c, csum = stack.pop()\n                    if c >= i:\n                        psum += c + csum\n                    total += c + csum\n                    ans = max(ans, (total)*c) \n            stack.append((i, psum))\n\n        # clean up the remaining stack\n        total = 0\n        while stack:\n            c, csum = stack.pop()\n            total += c + csum\n            ans = max(ans, (total)*c)\n        return ans % modulo\n```
['Monotonic Stack', 'Prefix Sum', 'Python3']