[Java] Monotonic Stack Solution, Time: O(N)
\n// Monotonic Stack Solution\n// The idea is same as Leetcode 84 "Largest Rectangle in Histogram"\n// 1. Get prefix sum array.\n// 2. While cur num is less tha
```\n// Monotonic Stack Solution\n// The idea is same as Leetcode 84 "Largest Rectangle in Histogram"\n// 1. Get prefix sum array.\n// 2. While cur num is less than the num in the top of stack, calculate the prod.\n// Time complexity: O(N)\n// Space complexity: O(N)\nclass Solution {\n    private static final int MOD = (int) 1E9 + 7;\n    public int maxSumMinProduct(int[] nums) {\n        if (nums == null || nums.length == 0) return 0;\n        final int N = nums.length;\n        long[] sums = new long[N+1];\n        for (int i = 1; i <= N; i++) {\n            sums[i] = sums[i-1] + nums[i-1];\n        }\n        long res = Long.MIN_VALUE;\n        Deque<Integer> stack = new ArrayDeque<>();\n        for (int i = 0; i <= N; i++) {\n            int cur = i == N ? 0 : nums[i];\n            while (!stack.isEmpty() && cur <= nums[stack.peek()]) {\n                int min = nums[stack.pop()];\n                int j = stack.isEmpty() ? 0 : stack.peek() + 1;\n                long sum = sums[i] - sums[j];\n                long prod = min * sum;\n                res = Math.max(res, prod);\n            }\n            stack.push(i);\n        }\n        return (int) (res % MOD);\n    }\n}\n```
['Java']