1856. Maximum Subarray Min-Product LeetCode Solution
In this guide, you will get 1856. Maximum Subarray Min-Product LeetCode Solution with the best time and space complexity. The solution to Maximum Subarray Min-Product problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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 109 + 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.
1856. Maximum Subarray Min-Product LeetCode Solution in C++
class Solution {
public:
int maxSumMinProduct(vector<int>& nums) {
constexpr int kMod = 1'000'000'007;
long ans = 0;
stack<int> stack;
vector<long> prefix(nums.size() + 1);
for (int i = 0; i < nums.size(); ++i)
prefix[i + 1] = prefix[i] + nums[i];
for (int i = 0; i <= nums.size(); ++i) {
while (!stack.empty() &&
(i == nums.size() || nums[stack.top()] > nums[i])) {
const int minVal = nums[stack.top()];
stack.pop();
const long sum =
stack.empty() ? prefix[i] : prefix[i] - prefix[stack.top() + 1];
ans = max(ans, minVal * sum);
}
stack.push(i);
}
return ans % kMod;
}
}; /* code provided by PROGIEZ */
1856. Maximum Subarray Min-Product LeetCode Solution in Java
class Solution {
public int maxSumMinProduct(int[] nums) {
final int kMod = 1_000_000_007;
long ans = 0;
Deque<Integer> stack = new ArrayDeque<>();
long[] prefix = new long[nums.length + 1];
for (int i = 0; i < nums.length; ++i)
prefix[i + 1] = prefix[i] + nums[i];
for (int i = 0; i <= nums.length; ++i) {
while (!stack.isEmpty() && (i == nums.length || nums[stack.peek()] > nums[i])) {
final int minVal = nums[stack.pop()];
final long sum = stack.isEmpty() ? prefix[i] : prefix[i] - prefix[stack.peek() + 1];
ans = Math.max(ans, minVal * sum);
}
stack.push(i);
}
return (int) (ans % kMod);
}
} // code provided by PROGIEZ
1856. Maximum Subarray Min-Product LeetCode Solution in Python
class Solution:
def maxSumMinProduct(self, nums: list[int]) -> int:
ans = 0
stack = []
prefix = list(itertools.accumulate(nums, initial=0))
for i in range(len(nums) + 1):
while stack and (i == len(nums) or nums[stack[-1]] > nums[i]):
minVal = nums[stack.pop()]
summ = prefix[i] - prefix[stack[-1] + 1] if stack else prefix[i]
ans = max(ans, minVal * summ)
stack.append(i)
return ans % int(1e9 + 7) # code by PROGIEZ
