Maximum Subarray Min-Product

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:

1. We treat nums[i] as minimum number in subarray which includes nums[i]
2. ans = max(ans, nums[i] * getSum(left_bound_index, right_bound_index))
3. left_bound_index: index of the farthest element greater or equal to nums[i] in the left side
4. 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?

1. Use stack st which keeps index of elements less than nums[i] so far
2. For i in [0..n-1]:
3. Pop all elements from st which are greater or equal to nums[i]
4. If st is not empty: left_bound[i] = st[-1] + 1 (because st[-1] is index of the nearest element smaller than nums[i])
5. else: left_bound[i] = 0 (because there is no element smaller than nums[i] so far)
6. 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)