Java Stack O(n)
\npublic int maxSumMinProduct(int[] nums) {\n        long mod = 1000000007;\n        int n = nums.length;\n        long []dp = new long[n];\n        dp[0] = num
```\npublic int maxSumMinProduct(int[] nums) {\n        long mod = 1000000007;\n        int n = nums.length;\n        long []dp = new long[n];\n        dp[0] = nums[0];\n        for(int i=1;i<n;i++){\n            dp[i] = dp[i-1] + nums[i];\n        }\n        long ans = 0;\n        Stack<Integer> st = new Stack();\n        for(int i=0;i<nums.length;i++){\n            if(st.isEmpty()){\n                st.push(i);\n            }else{\n                while(!st.isEmpty() && nums[st.peek()] >= nums[i]){\n                    int top = st.pop();\n                    if(st.isEmpty()){\n                        ans = Math.max(ans, dp[i-1]*nums[top]);\n                    }else{\n                        ans = Math.max(ans, (dp[i-1] - dp[st.peek()])*nums[top]);\n                    }\n                }\n                st.push(i);\n            }\n        }\n        while(!st.isEmpty()){\n            int top = st.pop();\n            if(st.isEmpty()){\n                ans = Math.max(ans, dp[n-1]*nums[top]);\n            }else{\n                ans = Math.max(ans, (dp[n-1] - dp[st.peek()])*nums[top]);\n            }\n        }\n        return (int)(ans % mod);\n    }\n```
[]