[Java] O(N) - Prefix Sum & Next Smallest with Stack
\nclass Solution \n{\n    private final int MOD = 1000000007;\n    public int maxSumMinProduct(int[] nums) \n    {\n        long[] prefix = new long[nums.length
```\nclass Solution \n{\n    private final int MOD = 1000000007;\n    public int maxSumMinProduct(int[] nums) \n    {\n        long[] prefix = new long[nums.length + 1];\n        long max = 0;\n        \n        for(int i = 1; i <= nums.length; i++)\n            prefix[i] = prefix[i - 1] + nums[i - 1];\n        \n        Stack<Integer> stack = new Stack<Integer>();\n\n        for(int i = 0; i < nums.length; i++)\n        {\n            while(stack.size() > 0 && nums[stack.peek()] >= nums[i])\n                max = Math.max(max, nums[stack.pop()] * FindRange(prefix, stack.size() > 0 ? stack.peek() + 1 : 0, i - 1));\n            \n            stack.push(i);\n        }\n        \n        while(stack.size() > 0)\n        {\n            int index = stack.pop();\n            \n            if(stack.size() > 0)\n                max = Math.max(max, nums[index] * (FindRange(prefix, stack.peek() + 1, index - 1) + FindRange(prefix, index, nums.length - 1)));\n            else\n                max = Math.max(max, nums[index] * prefix[nums.length]);\n        }\n        \n        return (int)(max % MOD);\n    }\n    \n    private long FindRange(long[] prefix, int x, int y)\n    {\n        if(x > y)\n            return 0;\n        \n        return prefix[y + 1] - prefix[x];\n    }\n}\n```
['Stack', 'Java']