Java easy stack
\nclass Solution {\n    public int maxSumMinProduct(int[] nums) {\n        int n = nums.length;\n        long[] prefixSum = new long[n + 1];\n        for (int i
```\nclass Solution {\n    public int maxSumMinProduct(int[] nums) {\n        int n = nums.length;\n        long[] prefixSum = new long[n + 1];\n        for (int i = 1; i <= n; i++) { // prefix Sum\n            prefixSum[i] = prefixSum[i - 1] + nums[i - 1];\n        }\n        Stack<Integer> stk1 = new Stack<>();\n        Stack<Integer> stk2 = new Stack<>();\n        int[] left = new int[n];\n        int[] right = new int[n];\n        for (int i = 0; i < n; i++) { // find the first element\' value < nums[i] in the left\n            while (!stk1.isEmpty() && nums[i] <= nums[stk1.peek()]) {\n                stk1.pop();\n            }\n            if (stk1.isEmpty()) {\n                left[i] = -1;\n            } else {\n                left[i] = stk1.peek();\n            }\n            stk1.push(i);\n        }\n        for (int i = n - 1; i >= 0; i--) { //  find the first element\' value < nums[i] in the right\n            while (!stk2.isEmpty() && nums[i] <= nums[stk2.peek()]) {\n                stk2.pop();\n            }\n            if (stk2.isEmpty()) {\n                right[i] = n;\n            } else {\n                right[i] = stk2.peek();\n            }\n            stk2.push(i);\n        }\n        long max = 0;\n        for (int i = 0; i < n; i++) { // make current element as Min value\n            int l = left[i];\n            int r = right[i];\n            long sum = prefixSum[r] - prefixSum[l + 1];\n            long prod = sum * nums[i];\n            max = Math.max(prod, max);\n        }\n        return (int)(max % 1_000_000_007);\n    }\n}\n```
[]