O(n) | C++ | stack
\nclass Solution {\npublic:\n    int maxSumMinProduct(vector<int>& nums) {\n        \n      int n =nums.size();\n      stack<int>st1;//prev min\n      stack<int
```\nclass Solution {\npublic:\n    int maxSumMinProduct(vector<int>& nums) {\n        \n      int n =nums.size();\n      stack<int>st1;//prev min\n      stack<int>st2;//next min\n      vector<int>prev(n,-1);\n      vector<int>next(n,-1);\n      \n      vector<long long int>pre(n+1,0);\n      \n      for(int i=0;i<n;i++){\n       \n          pre[i+1]=pre[i]+nums[i];\n        \n        \n        if(st1.empty()){\n           st1.push(i);\n        }else{\n        while(!st1.empty() && nums[i]< nums[st1.top()]){\n          st1.pop();\n        }\n        if(!st1.empty()){\n          prev[i]=st1.top();\n        }\n        st1.push(i);\n        }\n        \n        if(st2.empty()){\n          st2.push(i);\n        }else{\n    \n          while(!st2.empty() && nums[i]< nums[st2.top()]){\n          next[st2.top()]=i;\n          st2.pop();\n        }\n          st2.push(i);\n        \n        \n        }\n        \n      }\n      int s,e;\n      long long int ans=0;\n      for(int i=0;i<n;i++){\n        if(next[i]==-1){\n          e=n-1;\n        }else{\n          e=next[i]-1;\n        }\n        \n        if(prev[i]==-1){\n          s=0;\n        }else{\n          s=prev[i]+1;\n        }\n        \n        ans= max(ans, 1ll*nums[i] * (pre[e+1]-pre[s]) );\n   \n        \n      }\n    \n      return ans%1000000007;\n      \n    }\n};\n\n```
['Stack', 'C']