C++ | Prefix sum + stack | Similar to max rectangle in histogram
\nclass Solution {\npublic:\n    #define ll long\n    int mod=1000000007;\n    int maxSumMinProduct(vector<int>& nums) \n    {\n        ll n=nums.size(),res=0;\
```\nclass Solution {\npublic:\n    #define ll long\n    int mod=1000000007;\n    int maxSumMinProduct(vector<int>& nums) \n    {\n        ll n=nums.size(),res=0;\n        vector<ll>prefix(n+1,0);\n        for(int i=0;i<n;i++)\n            prefix[i+1]=prefix[i]+nums[i];\n        nums.push_back(0);\n        stack<int>stk;\n        for(int i=0;i<=n;i++)\n        {\n            while(!stk.empty() && nums[i]<nums[stk.top()])\n            {\n                int top=stk.top();stk.pop();\n                if(stk.empty())\n                {\n                    res=max(res,prefix[i]*nums[top]);\n                }\n                else\n                {\n                    ll sum=prefix[i]-prefix[stk.top()+1];\n                    res=max(res,sum*nums[top]);\n                }\n            }\n            stk.push(i);\n        }\n        return res%mod;\n    }\n};\n```
[]