✅ Just find NSL & NSR | Simple C++ |
give chance to every elem to be that min elem\n\nnow to what extent it has  its influence to its left ? until it finds a smaller elem than itself .\nso find nea
**give chance to every elem to be that min elem**\n\n**now to what extent it has  its influence to its left ? until it finds a smaller elem than itself .\nso find nearest smaller to left**\n\n**now to what extent it has  its influence to its right ? until it finds a greater elem than itself .\nso find nearest smaller to right**\n\n\n```\n#define ll long long\nclass Solution {\npublic:int mod = 1e9+7;\n    int maxSumMinProduct(vector<int>& a) {\n        ll n = a.size(),sum = 0,ans = 0; stack<int> s;\n        vector<ll> nsl(n) , nsr(n),pref(n);\n        \n\t\t//compute prefsix sum\n        for(int i = 0;i<n;i++){ \n            sum+=a[i]; pref[i] = sum;\n        }\n\t\t\n\t\t//compute next smaller to  left\n        \n        for(int i = 0;i<n;i++){\n            while(s.size() and a[s.top()] >= a[i]) s.pop();\n            \n            if(s.size()==0) nsl[i] = -1;\n            else nsl[i] = s.top();\n            \n            s.push(i);\n        }\n        \n        //there is no clear in stack so empty by popping\n        while(s.size()) s.pop();\n        \n\t\t//compute next smaller to  right\n\t\t\n        for(int i = n-1;i>=0;i--){\n            while(s.size() and a[s.top()]>=a[i]) s.pop();\n    \n            if(s.size()==0) nsr[i] = n;\n            else nsr[i] = s.top();\n            \n            s.push(i);\n        }\n        \n\t\t//Compute the required answer\n\t\t\n        for(int i = 0;i<n;i++){\n            int min_elem = a[i]; int l = nsl[i] , r = nsr[i];\n            \n            ll sum = pref[r-1] - (l==-1? 0 : pref[l]);\n            \n            ans = max(ans, min_elem*sum); \n        }\n        return ans%mod;\n    }\n};\n\n```
[]