Maximum Subarray Min-Product
给一个数组, 求里面最大的子数组中, 最小元素*子数组和的乘积.
把每个元素看做子数组的最小元素, 这样就变成求由这个元素组成的最长子数组. 用以前的https://leetcode.com/problems/next-greater-element-ii/solution/ 中的stack方法, 找到所求子数组的左界和右界.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
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); } } |