JavaO(n), one pass only, 13ms, 99.55%, 49.9MB memo, 100%
Please upvote if you find this Solution helpful, thank you!\nWe only need 1 monotonic decreasing stack to get both the left and right boundary of each min value
Please upvote if you find this Solution helpful, thank you!\nWe only need 1 monotonic decreasing stack to get both the left and right boundary of each min value. (i.e. each value in array)\n\nThis is very similar to:\n[2104. Sum of Subarray Ranges](https://leetcode.com/problems/sum-of-subarray-ranges/)\n[907. Sum of Subarray Minimums](https://leetcode.com/problems/sum-of-subarray-minimums/)\n```java\nclass Solution {\n    public int maxSumMinProduct(int[] a) {\n        int n = a.length, M = 1_000_000_007;\n        long res = 0L;\n\n        //step 1; get prefixs um\n        long [] psum = new long[n + 1];\n        for(int i = 0; i < n; i++) psum[i+1] = psum[i] + a[i];\n\n        //step 2: get the left and right bound of each sub-array using mono deceasing & increasing stack\n        int[] s = new int[n];\n        int top = -1; // mono-decreasing for right bound\n        for (int i = 0; i <= n; s[++top] = i++)\n            while (top >= 0 && (i == n || a[i] < a[s[top]])) {\n                int min = a[s[top--]]; // get curMin value and poll current index out of stack, it\'s left and right bouldary is not determined\n                int l = top == -1 ? 0 : s[top] + 1; // use the prev idx to get left bound, inclusive\n                int r = i - 1; // right bound, inclusive\n                res = Math.max(res, min * (psum[r+1] - psum[l]));\n            }\n\n        return (int) (res % M);\n    }\n}\n```
['Array', 'Stack', 'Prefix Sum', 'Java']