# 1856. Maximum Subarray Min-Product
###### tags: `Leetcode` `Medium` `Monotonic Stack` `Count Subarray by Element`
Link: https://leetcode.com/problems/maximum-subarray-min-product/
## 思路 $O(N)$ $O(N)$
和[1383. Maximum Performance of a Team](https://hackmd.io/bKCHp-8yTLi42s5emUM0WQ)以及[0857. Minimum Cost to Hire K Workers](https://hackmd.io/Ssaze_deSyi6x6qnHjWwHw)有点像
但差别在于上面两题不是找subarray
和[0907. Sum of Subarray Minimums](https://hackmd.io/EyszVtjHSKmgqUQCIn-t-A)很像

相当于是找next smaller 所以是用increasing stack
在每次找到next smaller时，用**以stack当前的max,** (也就是stack.peek()) **为最小值的array的min-product**更新答案
这个min-product就等于stack.peek()对应的值$*$ stack的下一个peek的位置（比目前的stack.peek()小）到next smaller的长度
## Code

class Solution {
    public int maxSumMinProduct(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        long[] prefixSum = new long[nums.length+1];
        long ans = 0;
        for(int i=0; i<nums.length; i++){
            prefixSum[i+1] = prefixSum[i]+nums[i];
        }
        for(int i=0; i<=nums.length; i++){
            while(!stack.isEmpty() && (i==nums.length || nums[stack.peek()]>nums[i])){
                int j = stack.pop();
                ans = Math.max(ans, nums[j]*(prefixSum[i]-prefixSum[stack.isEmpty()?0:(stack.peek()+1)]));
            }
            stack.push(i);
        }
        return (int)(ans%1000000007);
    }
}