C++ | Next Smaller Element | Stack
cpp\n#define ll long long\nclass Solution {\npublic:\n    ll mod = 1e9+7;\n    int maxSumMinProduct(vector<int>& a) {\n        ll ans = 0, n = a.size();\n      
```cpp\n#define ll long long\nclass Solution {\npublic:\n    ll mod = 1e9+7;\n    int maxSumMinProduct(vector<int>& a) {\n        ll ans = 0, n = a.size();\n        \n        // calculating prefix sum\n        vector<ll> pre(n+1, 0);\n        for(int i=1; i<=n; i++)\n            pre[i] = pre[i-1] + a[i-1];\n        \n        vector<int> lef(n), rig(n);\n        \n        // storing index of leftmost element which is >= current element\n        stack<int> s;\n        for(int i=0; i<n; i++)\n        {\n            while(!s.empty() && (a[s.top()] >= a[i]))\n                s.pop();       \n            if(s.empty()) lef[i] = 0;\n            else lef[i] = s.top()+1;\n            s.push(i);\n        }\n        while(!s.empty()) s.pop();\n        \n        // storing index of rightmost element which is >= current element\n        for(int i=n-1; i>=0; i--)\n        {\n            while(!s.empty() && (a[s.top()] >= a[i]))\n                s.pop();\n            \n            if(s.empty()) rig[i] = n-1;\n            else rig[i] = s.top() - 1;\n            s.push(i);\n        }\n        \n        // calculating ans, considering each element as min element\n        for(int i=0; i<n; i++)\n        {\n            ll sum = pre[rig[i]+1] - pre[lef[i]];\n            ans = max(ans, sum * a[i]);\n        }\n        return ans%mod;\n    }\n};\n```
['Stack', 'C']