[python3]monostack and prefix sum with detailed explanation
Core:\nRecommend trying https://leetcode.com/problems/largest-rectangle-in-histogram first.\nThen use monotonic stack with prefix sum.\n\nThe core is we know th
# Core:\nRecommend trying https://leetcode.com/problems/largest-rectangle-in-histogram first.\nThen use monotonic stack with prefix sum.\n\nThe core is we know the sum of subarray easily by using prefix sum.\n**But the minimal number of subarray is hard to know.**\n\nmonostack is hard for me to understand. So I hope I can help other.\n\nIncreasing monostack: A stack with non-decreasing order.\nWhy can monostack help us? \n**Monostack can easily help us find that the number v is the minimal number between index i and j with O(N) time like a magic.**\n\nWhenever we iterate the nums one by one and find a number A smaller than the stack top number B. Pop all the number larger than A in the stack.\n\nTo be clear, the index here is the index of number in the nums.\nnumber A index i\npop number B index i - 1\nthe previous number C in the monostack with index x\nC < B\nA < B\nC is the most recent number smaller than B.\nAny number after C must be larger than or equal to B.\n**B is the smallest number in this closed interval [x + 1, i -1]**\n\nsubarray min-product: sum(nums[x+1: i]) * B\n**If we can try every number as the min number with the interval as wide as possible(since nums[i] > 1), we will guarantee the result.**\n\n\nTake 1 3 6 5 2 for example.\nThe moment we iterate to value 2(index 4).\n\nThe current monostack (In the code only index . Value here is easy for readers to understand the concept.)\nindex [0, 1, 3]\nvalue [1, 3, 5]\n\npop 5\nnew monostack\nindex [0, 1]\nvalue [1, 3]\npop value 5 means 5 is the smallest number between (monostack[-1] + 1) and ((index 4) - 1) which are 2 and 3\t\t\t\t\t\t\t\t\t\t\t\t\t\t\nnew monostack\nindex [0]\nvalue [1]\npop value 3 means 3 in the smallest number between (monostack[-1] + 1) and ((index 4) - 1) which are 1 and 3\n\n# A trick here:\nAdd 0 to the end of nums array. We won\'t miss the edge case of increasing array. At the same time 0 < any number in nums\nAdd -1 to the monostack to avoid the first num compare with the empty mono_stack. \nmonostack[-1] == -1      nums[-1] == 0\nThere is no way to find a number in nums less than the last number of nums.\n\n# Full walkthrough:\nTake 1 3 5 2 1 for example.\nAdd 0 to the end. New array is 1 3 5 2 1 0.\n\nTo make the monostack easy to understand, I use the value in the stack for explanation. \nBut in the code the index is saved in the stack so that we can calculate the sum of subarray with left index and right index.\n```\nStack\t\tCompare \tAction\t\tsubarray min-product\n0\t\t\t\n0 1        \t1 > 0\t\tappend 1\n0 1 3\t\t3 > 1\t\tappend 3\n0 1 3 5\t\t5 > 3\t\tappend 5\n0 1 3 \t\t2 < 5 \t\tpop 5\t\t5 * 5\n0 1\t\t\t2 < 3 \t\tpop 3\t\t3 * (3 + 5)\n0 1 2\t\t\t\t\tappend 2\n0 1\t\t\t1 < 2\t\tpop 2\t\t2 * (3 + 5 + 2)\n0 1 1\t\t\t\t\tappend 1\n0 1\t\t\t0 < 1\t\tpop 1\t\t1 * (3 + 5 + 2 + 1)\n0\t\t\t0 < 1\t\tpop 1\t\t1 * (3 + 5 + 2 + 1)\n0 0\t\t\t\t\t\tappend 0\n\nResult 25\n```\n\n\n\n# Code\n```\nclass Solution:\n    def maxSumMinProduct(self, nums: List[int]) -> int:\n        n = len(nums)\n            \n        prefix_sum = [0]\n        for i in range(n):\n            prefix_sum.append(prefix_sum[-1] + nums[i])\n        \n        def subarray_sum(left, right):\n            return prefix_sum[right + 1] - prefix_sum[left]\n        \n        nums.append(0)\n        mono_stack = [-1]\n        \n        res = 0\n        for i in range(n + 1):\n            while nums[i] < nums[mono_stack[-1]]:\n                next_larger = mono_stack.pop()\n                res = max(res, nums[next_larger] * subarray_sum(mono_stack[-1] + 1, i - 1))\n            mono_stack.append(i)\n        return res % (10 ** 9 + 7)\n```
['Monotonic Stack']