Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1856.html

1856. Maximum Subarray Min-Product

Level

Medium

Description

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.

Given an array of integers nums, return the maximum min-product of any non-empty subarray of nums. Since the answer may be large, return it modulo 10^9 + 7.

Note that the min-product should be maximized before performing the modulo operation. Testcases are generated such that the maximum min-product without modulo will fit in a 64-bit signed integer.

A subarray is a contiguous part of an array.

Example 1:

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.

Example 2:

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.

Example 3:

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.

Constraints:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^7

Solution

First, calculate the prefix sums of nums, which can be used to calculate range sums effectively.

Then, use monotonic stack to find the left boundary and the right boundary of each nums[i]. That is, left[i] is the rightmost index such that left[i] < i and nums[left[i]] > nums[i], and right[i] is the leftmost index such that right[i] > i and nums[right[i]] > nums[i]. Then for each 0 <= i < nums.length, the product that has nums[i] as the minimum value is the range sum from left[i] + 1 to right[i] - 1 multiplied by nums[i]. Loop over i from 0 to nums.length - 1 to obtain the maximum subarray min-product.

  • class Solution {
    public int maxSumMinProduct(int[] nums) {
        final int MODULO = 1000000007;
        int length = nums.length;
        long[] prefixSums = new long[length + 1];
        for (int i = 0; i < length; i++)
            prefixSums[i + 1] = prefixSums[i] + (long) nums[i];
        int[] left = new int[length];
        int[] right = new int[length];
        Deque<Integer> stack = new LinkedList<Integer>();
        for (int i = 0; i < length; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
                stack.pop();
            }
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        stack.clear();
        for (int i = length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i])
                stack.pop();
            right[i] = stack.isEmpty() ? length : stack.peek();
            stack.push(i);
        }
        long maxProduct = 0;
        for (int i = 0; i < length; i++) {
            int leftIndex = left[i], rightIndex = right[i];
            long rangeSum = getRangeSum(prefixSums, leftIndex + 1, rightIndex - 1);
            long product = rangeSum * (long) nums[i];
            maxProduct = Math.max(maxProduct, product);
        }
        return (int) (maxProduct % MODULO);
    }

    public long getRangeSum(long[] prefixSums, int start, int end) {
        return prefixSums[end + 1] - prefixSums[start];
    }
}

############

class Solution {
    public int maxSumMinProduct(int[] nums) {
        int n = nums.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(left, -1);
        Arrays.fill(right, n);
        Deque<Integer> stk = new ArrayDeque<>();
        for (int i = 0; i < n; ++i) {
            while (!stk.isEmpty() && nums[stk.peek()] >= nums[i]) {
                stk.pop();
            }
            if (!stk.isEmpty()) {
                left[i] = stk.peek();
            }
            stk.push(i);
        }
        stk.clear();
        for (int i = n - 1; i >= 0; --i) {
            while (!stk.isEmpty() && nums[stk.peek()] > nums[i]) {
                stk.pop();
            }
            if (!stk.isEmpty()) {
                right[i] = stk.peek();
            }
            stk.push(i);
        }
        long[] s = new long[n + 1];
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + nums[i];
        }
        long ans = 0;
        for (int i = 0; i < n; ++i) {
            long t = nums[i] * (s[right[i]] - s[left[i] + 1]);
            ans = Math.max(ans, t);
        }
        return (int) (ans % 1000000007);
    }
}

  • class Solution:
    def maxSumMinProduct(self, nums: List[int]) -> int:
        mod = int(1e9) + 7
        n = len(nums)
        left = [-1] * n
        right = [n] * n
        stk = []
        for i, v in enumerate(nums):
            while stk and nums[stk[-1]] >= v:
                stk.pop()
            if stk:
                left[i] = stk[-1]
            stk.append(i)
        stk = []
        for i in range(n - 1, -1, -1):
            while stk and nums[stk[-1]] > nums[i]:
                stk.pop()
            if stk:
                right[i] = stk[-1]
            stk.append(i)
        s = [0] + list(accumulate(nums))
        ans = max(v * (s[right[i]] - s[left[i] + 1]) for i, v in enumerate(nums))
        return ans % mod

############

# 1856. Maximum Subarray Min-Product
# https://leetcode.com/problems/maximum-subarray-min-product

class Solution:
    def maxSumMinProduct(self, nums: List[int]) -> int:
        M = 10 ** 9 + 7
        n = len(nums)
        res = 0
        
        prefix = [0]
        for x in nums:
            prefix.append(x + prefix[-1])
        
        l = [0] * n
        r = [0] * n
        stack = []
        
        for i in range(n):
            while stack and nums[stack[-1]] >= nums[i]:
                stack.pop()
            
            if stack:
                l[i] = stack[-1] + 1
            else:
                l[i] = 0
                
            stack.append(i)
        
        stack = []
        
        for i in reversed(range(n)):
            while stack and nums[stack[-1]] >= nums[i]:
                stack.pop()
            
            if stack:
                r[i] = stack[-1] - 1
            else:
                r[i] = n - 1
            
            stack.append(i)
        
        for i in range(n):
            res = max(res, nums[i] * (prefix[r[i] + 1] - prefix[l[i]]))
        

        return res % M


  • class Solution {
public:
    int maxSumMinProduct(vector<int>& nums) {
        int n = nums.size();
        vector<int> left(n, -1);
        vector<int> right(n, n);
        stack<int> stk;
        for (int i = 0; i < n; ++i) {
            while (!stk.empty() && nums[stk.top()] >= nums[i]) stk.pop();
            if (!stk.empty()) left[i] = stk.top();
            stk.push(i);
        }
        stk = stack<int>();
        for (int i = n - 1; i >= 0; --i) {
            while (!stk.empty() && nums[stk.top()] > nums[i]) stk.pop();
            if (!stk.empty()) right[i] = stk.top();
            stk.push(i);
        }
        vector<long long> s(n + 1);
        for (int i = 0; i < n; ++i) s[i + 1] = s[i] + nums[i];
        long long ans = 0;
        const int mod = 1e9 + 7;
        for (int i = 0; i < n; ++i) {
            long long t = nums[i] * (s[right[i]] - s[left[i] + 1]);
            ans = max(ans, t);
        }
        return (int) (ans % mod);
    }
};

  • func maxSumMinProduct(nums []int) int {
	n := len(nums)
	left := make([]int, n)
	right := make([]int, n)
	for i := range left {
		left[i] = -1
		right[i] = n
	}
	stk := []int{}
	for i, v := range nums {
		for len(stk) > 0 && nums[stk[len(stk)-1]] >= v {
			stk = stk[:len(stk)-1]
		}
		if len(stk) > 0 {
			left[i] = stk[len(stk)-1]
		}
		stk = append(stk, i)
	}
	stk = []int{}
	for i := n - 1; i >= 0; i-- {
		for len(stk) > 0 && nums[stk[len(stk)-1]] > nums[i] {
			stk = stk[:len(stk)-1]
		}
		if len(stk) > 0 {
			right[i] = stk[len(stk)-1]
		}
		stk = append(stk, i)
	}
	s := make([]int, n+1)
	for i, v := range nums {
		s[i+1] = s[i] + v
	}
	ans := 0
	for i, v := range nums {
		t := v * (s[right[i]] - s[left[i]+1])
		if ans < t {
			ans = t
		}
	}
	mod := int(1e9) + 7
	return ans % mod
}

  • function maxSumMinProduct(nums: number[]): number {
    const n = nums.length;
    const left: number[] = new Array(n).fill(-1);
    const right: number[] = new Array(n).fill(n);
    let stk: number[] = [];
    for (let i = 0; i < n; ++i) {
        while (stk.length && nums[stk[stk.length - 1]] >= nums[i]) {
            stk.pop();
        }
        if (stk.length) {
            left[i] = stk[stk.length - 1];
        }
        stk.push(i);
    }
    stk = [];
    for (let i = n - 1; i >= 0; --i) {
        while (stk.length && nums[stk[stk.length - 1]] > nums[i]) {
            stk.pop();
        }
        if (stk.length) {
            right[i] = stk[stk.length - 1];
        }
        stk.push(i);
    }
    const s: number[] = new Array(n + 1).fill(0);
    for (let i = 0; i < n; ++i) {
        s[i + 1] = s[i] + nums[i];
    }
    let ans: bigint = 0n;
    const mod = 10 ** 9 + 7;
    for (let i = 0; i < n; ++i) {
        const t = BigInt(nums[i]) * BigInt(s[right[i]] - s[left[i] + 1]);
        if (ans < t) {
            ans = t;
        }
    }
    return Number(ans % BigInt(mod));
}

All Problems

All Solutions