[Java] Stack Time: O(n)
For this problem, we want to use each number in nums as min value. And expand to both left and right. On the right we want to find the first index that is small
For this problem, we want to use each number in `nums` as `min` value. And expand to both left and right. On the right we want to find the first index that is smaller than `nums[i]`. And similar for left, we want to find the first index on the left whose corresponding value  is smaller than `nums[i]`. \n\nWe use stack to get both the first left index and first right index.\n\nTime: `O(n)`\nSpace: `O(n)`\n\n```\nclass Solution {\n    public int maxSumMinProduct(int[] nums) {\n        //for this problem, we can quickly know the sum of an subarray with prefix sum array\n        //so the difficult point is how to get the min value for each array very quickly\n        //we can use segment tree\n        //but this still O(N^2), since you will find for each pair of [i, j]\n        //we can focus on each number in nums, let it be the min and we expand from this number to right and to left\n        //we want to ask what is the first number on the right that is smaller than this number\n        //and what is the first number on the left that is smaller than this number\n        int n = nums.length;\n        int mod = (int)(1e9 + 7);\n        if (n == 1) return (int)(((long)nums[0] * (long)nums[0]) % mod);\n        int[] left = new int[n];\n        Stack<Integer> st = new Stack<>();\n        for (int i = 0; i < n; i++) {\n            while (!st.isEmpty() && nums[st.peek()] >= nums[i]) {\n                st.pop();\n            }\n            if (st.isEmpty()) left[i] = -1;\n            else left[i] = st.peek();\n            st.add(i);\n        }\n        int[] right = new int[n];\n        st = new Stack<>();\n        for (int i = n-1; i >= 0; i--) {\n            while (!st.isEmpty() && nums[st.peek()] >= nums[i]) {\n                st.pop();\n            }\n            if (st.isEmpty()) right[i] = n;\n            else right[i] = st.peek();\n            st.add(i);\n        }\n\n        long res = 0L;\n        long[] preSum = new long[n];\n        preSum[0] = (long)nums[0];\n        for (int i = 1; i < n; i++) {\n            preSum[i] = preSum[i-1] + (long)nums[i];\n        }\n        for (int i = 0; i < n; i++) {\n            long sum = left[i] == -1 ? preSum[right[i]-1] : preSum[right[i]-1] - preSum[left[i]];\n            long cur = (long)nums[i] * sum;\n            res = Math.max(cur, res);\n        }\n        return (int)(res % mod);\n    }\n}\n```\n\nSimilar Stack problems:\n\n1. https://leetcode.com/problems/largest-rectangle-in-histogram/\n2. https://leetcode.com/problems/sum-of-subarray-minimums/\n3. https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/\n4. https://leetcode.com/problems/sliding-window-maximum/
[]