Maximum Subarray Min-Product

给一个数组, 求里面最大的子数组中, 最小元素*子数组和的乘积.

把每个元素看做子数组的最小元素, 这样就变成求由这个元素组成的最长子数组. 用以前的https://leetcode.com/problems/next-greater-element-ii/solution/ 中的stack方法, 找到所求子数组的左界和右界.

class Solution {
    public int maxSumMinProduct(int[] nums) {
        int[] left = new int[nums.length];
        int[] right = new int[nums.length];
        Stack<Integer>lt=new Stack<>();
        Stack<Integer>rt=new Stack<>();
        Arrays.fill(left, -1); // fill with left edge
        Arrays.fill(right, nums.length);// fill with right edge
        for(int i=0;i<nums.length;i++)
        {
            while(rt.size()!=0 && nums[rt.peek()] > nums[i])
            {
              right[rt.pop()]= i;
            }
            rt.push(i);
        }
        for(int i= nums.length - 1;i >= 0;i--)
        {
            while(lt.size()!=0 && nums[lt.peek()] > nums[i])
            {
              left[lt.pop()]= i;
            }
            lt.push(i);
        }
        long[] pre = new long[nums.length + 1];
        for(int i = 1; i < nums.length + 1; i++){
            pre[i] = pre[i - 1] + nums[i - 1];
        }
        
        long sum = 0;
        int mod = (int) Math.pow(10,9) + 7;
        for(int i = 0; i < nums.length; i++) { 
            sum = Math.max(sum, nums[i] * (pre[right[i]] - pre[left[i] + 1]) );
        }
        return (int) (sum % mod);
    }
}