Solution with Three Example Explanation
Exp1\n\nYour input\n[1,2,3,2]\nYour stdout\nselect value= 1\nrunning_sum= 1\nstack= [(-1, 0), (1, 1)]\n\nselect value= 2\nrunning_sum= 3\nstack= [(-1, 0), (1, 1
# Exp1\n```\nYour input\n[1,2,3,2]\nYour stdout\nselect value= 1\nrunning_sum= 1\nstack= [(-1, 0), (1, 1)]\n\nselect value= 2\nrunning_sum= 3\nstack= [(-1, 0), (1, 1), (2, 3)]\n\nselect value= 3\nrunning_sum= 6\nstack= [(-1, 0), (1, 1), (2, 3), (3, 6)]\n\nselect value= 2\nstack[-1][0]>=selectvalue True\npop minvalue= 3 running sum= 6 stack[-1][1] 3\n[(-1, 0), (1, 1), (2, 3)]\nrunning_max 9\n\nstack[-1][0]>=selectvalue True\npop minvalue= 2 running sum= 6 stack[-1][1] 1\n[(-1, 0), (1, 1)]\nrunning_max 10\n\nrunning_sum= 8\nstack= [(-1, 0), (1, 1), (2, 8)]\n\nselect value= 0\nstack[-1][0]>=selectvalue True\npop minvalue= 2 running sum= 8 stack[-1][1] 1\n[(-1, 0), (1, 1)]\nrunning_max 14\n\nstack[-1][0]>=selectvalue True\npop minvalue= 1 running sum= 8 stack[-1][1] 0\n[(-1, 0)]\nrunning_max 14\n\nrunning_sum= 8\nstack= [(-1, 0), (0, 8)]\n\n\nYour answer\n14\nExpected answer\n14\n```\n# Ex2\n```\n\n\nYour input\n[2,3,3,1,2]\nYour stdout\nselect value= 2\nrunning_sum= 2\nstack= [(-1, 0), (2, 2)]\n\nselect value= 3\nrunning_sum= 5\nstack= [(-1, 0), (2, 2), (3, 5)]\n\nselect value= 3\nstack[-1][0]>=selectvalue True\npop minvalue= 3 running sum= 5 stack[-1][1] 2\n[(-1, 0), (2, 2)]\nrunning_max 9\n\nrunning_sum= 8\nstack= [(-1, 0), (2, 2), (3, 8)]\n\nselect value= 1\nstack[-1][0]>=selectvalue True\npop minvalue= 3 running sum= 8 stack[-1][1] 2\n[(-1, 0), (2, 2)]\nrunning_max 18\n\nstack[-1][0]>=selectvalue True\npop minvalue= 2 running sum= 8 stack[-1][1] 0\n[(-1, 0)]\nrunning_max 18\n\nrunning_sum= 9\nstack= [(-1, 0), (1, 9)]\n\nselect value= 2\nrunning_sum= 11\nstack= [(-1, 0), (1, 9), (2, 11)]\n\nselect value= 0\nstack[-1][0]>=selectvalue True\npop minvalue= 2 running sum= 11 stack[-1][1] 9\n[(-1, 0), (1, 9)]\nrunning_max 18\n\nstack[-1][0]>=selectvalue True\npop minvalue= 1 running sum= 11 stack[-1][1] 0\n[(-1, 0)]\nrunning_max 18\n\nrunning_sum= 11\nstack= [(-1, 0), (0, 11)]\n\n\nYour answer\n18\nExpected answer\n18\n```\n\n\n# Ex:3\n```\n\n\nYour input\n [3,1,5,6,4,2]\nYour stdout\nselect value= 3\nrunning_sum= 3\nstack= [(-1, 0), (3, 3)]\n\nselect value= 1\nstack[-1][0]>=selectvalue True\npop minvalue= 3 running sum= 3 stack[-1][1] 0\n[(-1, 0)]\nrunning_max 9\n\nrunning_sum= 4\nstack= [(-1, 0), (1, 4)]\n\nselect value= 5\nrunning_sum= 9\nstack= [(-1, 0), (1, 4), (5, 9)]\n\nselect value= 6\nrunning_sum= 15\nstack= [(-1, 0), (1, 4), (5, 9), (6, 15)]\n\nselect value= 4\nstack[-1][0]>=selectvalue True\npop minvalue= 6 running sum= 15 stack[-1][1] 9\n[(-1, 0), (1, 4), (5, 9)]\nrunning_max 36\n\nstack[-1][0]>=selectvalue True\npop minvalue= 5 running sum= 15 stack[-1][1] 4\n[(-1, 0), (1, 4)]\nrunning_max 55\n\nrunning_sum= 19\nstack= [(-1, 0), (1, 4), (4, 19)]\n\nselect value= 2\nstack[-1][0]>=selectvalue True\npop minvalue= 4 running sum= 19 stack[-1][1] 4\n[(-1, 0), (1, 4)]\nrunning_max 60\n\nrunning_sum= 21\nstack= [(-1, 0), (1, 4), (2, 21)]\n\nselect value= 0\nstack[-1][0]>=selectvalue True\npop minvalue= 2 running sum= 21 stack[-1][1] 4\n[(-1, 0), (1, 4)]\nrunning_max 60\n\nstack[-1][0]>=selectvalue True\npop minvalue= 1 running sum= 21 stack[-1][1] 0\n[(-1, 0)]\nrunning_max 60\n\nrunning_sum= 21\nstack= [(-1, 0), (0, 21)]\n\n\nYour answer\n60\nExpected answer\n60\n```\n\n```\n\nYour input\n\n[2,5,4,2,4,5,3,1,2,4]\nYour stdout\nselect value= 2\nrunning_sum= 2\nstack= [(-1, 0), (2, 2)]\n\nselect value= 5\nrunning_sum= 7\nstack= [(-1, 0), (2, 2), (5, 7)]\n\nselect value= 4\nstack[-1][0]>=selectvalue True\npop minvalue= 5 running sum= 7 stack[-1][1] 2\n[(-1, 0), (2, 2)]\nrunning_max 25\n\nrunning_sum= 11\nstack= [(-1, 0), (2, 2), (4, 11)]\n\nselect value= 2\nstack[-1][0]>=selectvalue True\npop minvalue= 4 running sum= 11 stack[-1][1] 2\n[(-1, 0), (2, 2)]\nrunning_max 36\n\nstack[-1][0]>=selectvalue True\npop minvalue= 2 running sum= 11 stack[-1][1] 0\n[(-1, 0)]\nrunning_max 36\n\nrunning_sum= 13\nstack= [(-1, 0), (2, 13)]\n\nselect value= 4\nrunning_sum= 17\nstack= [(-1, 0), (2, 13), (4, 17)]\n\nselect value= 5\nrunning_sum= 22\nstack= [(-1, 0), (2, 13), (4, 17), (5, 22)]\n\nselect value= 3\nstack[-1][0]>=selectvalue True\npop minvalue= 5 running sum= 22 stack[-1][1] 17\n[(-1, 0), (2, 13), (4, 17)]\nrunning_max 36\n\nstack[-1][0]>=selectvalue True\npop minvalue= 4 running sum= 22 stack[-1][1] 13\n[(-1, 0), (2, 13)]\nrunning_max 36\n\nrunning_sum= 25\nstack= [(-1, 0), (2, 13), (3, 25)]\n\nselect value= 1\nstack[-1][0]>=selectvalue True\npop minvalue= 3 running sum= 25 stack[-1][1] 13\n[(-1, 0), (2, 13)]\nrunning_max 36\n\nstack[-1][0]>=selectvalue True\npop minvalue= 2 running sum= 25 stack[-1][1] 0\n[(-1, 0)]\nrunning_max 50\n\nrunning_sum= 26\nstack= [(-1, 0), (1, 26)]\n\nselect value= 2\nrunning_sum= 28\nstack= [(-1, 0), (1, 26), (2, 28)]\n\nselect value= 4\nrunning_sum= 32\nstack= [(-1, 0), (1, 26), (2, 28), (4, 32)]\n\nselect value= 0\nstack[-1][0]>=selectvalue True\npop minvalue= 4 running sum= 32 stack[-1][1] 28\n[(-1, 0), (1, 26), (2, 28)]\nrunning_max 50\n\nstack[-1][0]>=selectvalue True\npop minvalue= 2 running sum= 32 stack[-1][1] 26\n[(-1, 0), (1, 26)]\nrunning_max 50\n\nstack[-1][0]>=selectvalue True\npop minvalue= 1 running sum= 32 stack[-1][1] 0\n[(-1, 0)]\nrunning_max 50\n\nrunning_sum= 32\nstack= [(-1, 0), (0, 32)]\n\n\nYour answer\n50\nExpected answer\n50\n```\n\n\n\n```\n\n\nclass Solution:\n    def maxSumMinProduct(self, nums: List[int]) -> int:\n        stack = [(-1, 0)] # minimum value and running sum\n        running_max = running_sum = 0\n        nums.append(0)\n        for v in nums:\n            while stack[-1][0] >= v:\n                min_value, _ = stack.pop()\n                running_max = max(running_max, min_value * (running_sum - stack[-1][1]))\n            running_sum += v\n            stack.append((v, running_sum))\n        return running_max % (10**9+7)\n```
[]