Skip to content

1856. Maximum Subarray Min-Product 👍

  • Time: $O(n)$
  • Space: $O(n)$
 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
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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)