Maximum Subarray Min-Product LeetCode solution in Java

1
class Solution {
2
  public int maxSumMinProduct(int[] nums) {
3
    int mod = (int) Math.pow(10, 9) + 7;
4
    int n = nums.length;
5

6
    // next smaller on left
7
    int[] left = new int[n];
8
    Stack<Integer> st = new Stack<>();
9
    left[0] = -1;
10
    st.push(0);
11
    for (int i = 1; i < n; i++) {
12
      while (st.size() > 0 && nums[st.peek()] >= nums[i]) {
13
        st.pop();
14
      }
15

16
      if (st.size() == 0) left[i] = -1;
17
      else left[i] = st.peek();
18

19
      st.push(i);
20
    }
21

22
    // next smaller on right
23
    int[] right = new int[n];
24
    st = new Stack<>();
25
    right[n - 1] = n;
26
    st.push(n - 1);
27
    for (int i = n - 2; i >= 0; i--) {
28
      while (st.size() > 0 && nums[st.peek()] >= nums[i]) st.pop();
29

30
      if (st.size() > 0) right[i] = st.peek();
31
      else right[i] = n;
32

33
      st.push(i);
34
    }
35

36
    long[] prefixSum = new long[n];
37
    prefixSum[0] = nums[0];
38
    for (int i = 1; i < n; i++) prefixSum[i] = prefixSum[i - 1] + nums[i];
39

40
    long max = 0;
41
    for (int i = 0; i < nums.length; i++) {
42
      int l = left[i];
43
      int r = right[i] - 1;
44

45
      max = Math.max(max, (prefixSum[r] - (l == -1 ? 0 : prefixSum[l])) * nums[i]);
46
    }
47
    return (int) (max % mod);
48
  }
49
}