# 1856. Maximum Subarray Min-Product

same idea as 907

but presum part...I don't know why should use a n length (without presum\[0]) style

and becareful when index == -1 presum\[-1] means no sum => so it's 0

T: O(n)

S: O(n)

```java
class Solution {
    public int maxSumMinProduct(int[] nums) {
        int n = nums.length;
        long[] presum = new long[n];
        presum[0] = nums[0];
        for (int i = 1; i < n; i++) {
            presum[i] = presum[i-1] + nums[i];
        }
        System.out.println(Arrays.toString(presum));
        
        long mod = 1000000007;
        Deque<Integer> stack = new ArrayDeque<>();
        int[] nextSmaller = new int[n];
        int[] prevSmaller = new int[n];
        
        Arrays.fill(nextSmaller, n); // important
        Arrays.fill(prevSmaller, -1); // important
        
        // 1 4 7 2
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) { // when I found stack peek > new number, find smaller number! start to record and pop
                nextSmaller[stack.peek()] = i;
                stack.pop();
            }
            stack.push(i);
        }
        // System.out.println(Arrays.toString(nextSmaller));
        stack.clear();
        
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) { //去重的約定
                prevSmaller[stack.peek()] = i;
                stack.pop();
            }
            stack.push(i);
        }
        // System.out.println(Arrays.toString(prevSmaller)); 
        long result = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            long sum = presum[nextSmaller[i]-1] - (prevSmaller[i] == -1 ? 0 : presum[prevSmaller[i]]);
            System.out.println("num[i]:" + nums[i] + ",nextSmaller[i]:" + nextSmaller[i] + " prevSmaller[i]:" + prevSmaller[i] + ", sum=" + sum);
            
            result = Math.max(result, nums[i]*sum);
        }
        return (int)(result%mod);
    }
}
/*
1. use monostack, find nextSmaller, prevSmaller -> find min subarray range index array first
get each number as a min in a subarray's range

1 as min, => [4, 4, 3, 4]

2 3

3 2 [x,x, 3, x]
2 1
1 0

1
2 
 [-1,0,1,-1]
2


next[i] 4 - 0
prev0-(-1) = 1


sum[0,3] = presum[3+1] - presum[0]
=presum[next[i]]-[0]

2. then use presum -> cal subarray sum = presum[j+1] - presum[i]

 0 1 2 3 4 5 6 7
[2,5,4,2,4,5,3,1,2,4
*/
```

## aws oa

{% embed url="<https://leetcode.com/discuss/interview-question/1737071/Amazon-OA-or-SDE-or-90-Min>" %}

<https://leetcode.com/discuss/interview-question/1736639/Solution-to-Amazon-OA-2022-problem-Sum-of-Scores-of-Subarray>

![](/files/AuNsdnKGdOy5K3mdXb7f)

![](/files/acZwhDQAU6CpIHZPLQx5)

\[2,3,2,1]&#x20;

stdout&#x20;

\[3, 2, 3, 4]  next

\[-1, 0, 0, -1] prev

2 as min -> \[2,3,2], sum = 2, 5(2,3), 7(2,3,2),   5(3,2),  2

```java
class Solution {
    public int maxSumMinProduct(int[] arr) {
    
        int n = arr.length;
        Stack<Integer> stack = new Stack();
        long ans = 0;
        long[] sum = new long[n+1], sum1 = new long[n+1];//prefix sum and suffix sum
        long[] prefix = new long[n+1], suffix = new long[n+1];//prefix sum of prefixsum and suffix sum of suffixsum
        long mod = 1_000_000_007;
        for(int i = 0; i < n; i++)
        {
            sum[i+1] = (sum[i]+arr[i])%mod;
            prefix[i+1] = (prefix[i]+sum[i+1])%mod;
        }
        for(int i = n-1; i >= 0; i--)
        {
            sum1[i] = (sum1[i+1]+arr[i])%mod;
            suffix[i] = (suffix[i+1]+sum1[i])%mod;
        }
        
        for(int i = 0; i < n; i++)
        {
            while(!stack.isEmpty() && arr[stack.peek()] >= arr[i])
            {
                int cur =  stack.pop();
                int prev = stack.isEmpty() ? -1 : stack.peek();
                int next = i;
                //the commented lines shows how the left sum and right sum are calculated
                //Maybe a little hard to understand but the idea is similar
                //long lsum = suffix[prev+1]-suffix[cur]-sum1[cur]*(cur-prev-1)%mod;
                //long rsum = prefix[next]-prefix[cur+1]-sum[cur+1]*(next-cur-1)%mod;
                //below I takes modulo everytime there is multiplication and addition to avoid overflow in java
                long lsum = (mod+suffix[prev+1]-(suffix[cur]+sum1[cur]*(cur-prev-1)%mod)%mod)%mod;
                long rsum = (mod+prefix[next]-(prefix[cur+1]+sum[cur+1]*(next-cur-1)%mod)%mod)%mod;
                long self = ((long)arr[cur]*(next-cur)%mod)*(cur-prev)%mod;
                long curres = (long)arr[cur]*((rsum*(cur-prev)%mod+lsum*(next-cur)%mod+self)%mod)%mod;
                ans =(ans+curres)%mod;
            }
            stack.push(i);
        }
        while(!stack.isEmpty())//do the same thing for the remaining numbers
        {
            int cur = stack.pop();
            int prev = stack.isEmpty() ? -1 : stack.peek();
            int next = n;
            //comments are the same as previously
            long lsum = (mod+suffix[prev+1]-(suffix[cur]+sum1[cur]*(cur-prev-1))%mod)%mod;
            long rsum = (mod+prefix[next]-(prefix[cur+1]+sum[cur+1]*(next-cur-1))%mod)%mod;
            long self = ((long)arr[cur]*(next-cur)%mod)*(cur-prev)%mod;
            long curres = (long)arr[cur]*((rsum*(cur-prev)%mod+lsum*(next-cur)%mod+self)%mod)%mod;
            ans =(ans+curres)%mod;
        }
        return (int)ans;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/stack/mono-stack/1856.-maximum-subarray-min-product.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.