C++||Hard Level Problem Made Easy with Explanation
\ntypedef long long ll;\nll mod=1e9+7;\nclass Solution {\npublic:\n    int maxSumMinProduct(vector<int>& nums) {\n        int n=nums.size();\n        vector<ll>
```\ntypedef long long ll;\nll mod=1e9+7;\nclass Solution {\npublic:\n    int maxSumMinProduct(vector<int>& nums) {\n        int n=nums.size();\n        vector<ll> pref(n+1,0);//storing the prefix sum\n        pref[0]=0;\n        for(int i=1;i<=n;i++)\n        {\n            pref[i]=nums[i-1]+pref[i-1];\n        }\n        vector<ll> right(n);//for storing the index which is smallest in the right of index i\n        vector<ll> left(n);//for storing the index which is smallest in the left of index i\n        right[n-1]=n;\n        stack<ll> st1;\n        stack<ll>st2;\n        st1.push(n-1);\n        for(int i=n-2;i>=0;i--)\n        {\n            while(!st1.empty() and nums[st1.top()]>=nums[i])\n                st1.pop();\n            if(st1.empty())\n                right[i]=n;\n            else\n                right[i]=st1.top();\n            st1.push(i);\n        }\n        left[0]=-1;\n        st2.push(0);\n        for(int i=1;i<n;i++)\n        {\n            while(!st2.empty() and nums[i]<=nums[st2.top()])\n                st2.pop();\n            if(st2.empty())\n                left[i]=-1;\n            else\n                left[i]=st2.top();\n                st2.push(i);\n        }\n        ll maxi=INT_MIN;\n        for(int i=0;i<n;i++)\n        {\n            ll ans=(((pref[right[i]]-pref[left[i]+1]))*nums[i]);//considering  nums[i] smaller\n            maxi=max(maxi,ans);//then finding the corresponding subbarray sum multiplying with nums[i]\n        }                                  // and finding maximum by considering each element\n        return maxi%mod;\n    }\n};\n```
['Prefix Sum']