The min-product of an array is equal to the minimum value in the array multiplied by the array’s sum.
For example, the array [3,2,5] (minimum value is 2) has a min-product of 2 * (3+2+5) = 2 * 10 = 20.
A subarray is a contiguous part of an array.
Input: nums = [1,2,3,2] Output: 14 Explanation: The maximum min-product is achieved with the subarray [2,3,2] (minimum value is 2). 2 * (2+3+2) = 2 * 7 = 14. Input: nums = [2,3,3,1,2] Output: 18 Explanation: The maximum min-product is achieved with the subarray [3,3] (minimum value is 3). 3 * (3+3) = 3 * 6 = 18. Input: nums = [3,1,5,6,4,2] Output: 60 Explanation: The maximum min-product is achieved with the subarray [5,6,4] (minimum value is 4). 4 * (5+6+4) = 4 * 15 = 60.
Approach:
ans = 0
For each element nums[i] in array nums:
- We treat nums[i] as minimum number in subarray which includes nums[i]
- ans = max(ans, nums[i] * getSum(left_bound_index, right_bound_index))
- left_bound_index: index of the farthest element greater or equal to nums[i] in the left side
- right_bound_index: index of the farthest element greater or equal to nums[i] in the right side
How to build left_bound/right_bound array which store index of the farthest element greater or equal to nums[i] in the left side or in the right side?
- Use stack st which keeps index of elements less than nums[i] so far
- For i in [0..n-1]:
- Pop all elements from st which are greater or equal to nums[i]
- If st is not empty: left_bound[i] = st[-1] + 1 (because st[-1] is index of the nearest element smaller than nums[i])
- else: left_bound[i] = 0 (because there is no element smaller than nums[i] so far)
- Add i to st
Implementation in Java:
import java.util.*; public class Solution { long[] preSum; public int maxSumMinProduct(int[] nums) { int n = nums.length; int[] left_bound = new int[n], right_bound = new int[n]; Stack<Integer> st = new Stack<>(); for (int i = 0; i < n; ++i) { while (!st.isEmpty() && nums[st.peek()] >= nums[i]) st.pop(); if (!st.isEmpty()) left_bound[i] = st.peek() + 1; else left_bound[i] = 0; st.add(i); } st = new Stack<>(); for (int i = n - 1; i >= 0; --i) { while (!st.isEmpty() && nums[st.peek()] >= nums[i]) st.pop(); if (!st.isEmpty()) right_bound[i] = st.peek() - 1; else right_bound[i] = n - 1; st.add(i); } preSum = new long[n + 1]; for (int i = 0; i < n; ++i) preSum[i + 1] = preSum[i] + nums[i]; long maxProduct = 0; for (int i = 0; i < n; ++i) maxProduct = Math.max(maxProduct, getSum(left_bound[i], right_bound[i]) * nums[i]); return (int) (maxProduct % 1_000_000_007); } long getSum(int left, int right) { // left, right inclusive return preSum[right + 1] - preSum[left]; } public static void main(String[] args) { Solution st = new Solution(); int[] num = {1, 2, 3, 2}; int res = st.maxSumMinProduct(num); System.out.println(res); } }
Output:
14
Time complexity: O(N)
Spacecomplexity: O(N)