C++ solution in O(n) using stack with explanation
The basic idea of the solution is that, for a particular element we want to find the range in which it will act as the minimum element. And for that particular 
The basic idea of the solution is that, for a particular element we want to find the range in which it will act as the minimum element. And for that particular range we find the sum of the range and multiply it with this element and keep track of maximum of these values.\n\n1. Calculate the prefix and suffix sum of the given array.\n2. Now using stacks and the concept of next smaller element we find the index of the element just smaller than the given element, on the right as well as the left side in the array.\n3. Now iterating over the array and finding the index of smaller element on the left and the right side and using prefix and suffix sum we can calculate the sum for that given range.\n\nCode:\n\n```\n#define mod 1000000007\n    \n    int maxSumMinProduct(vector<int>& nums) {\n\t\n        int n=nums.size();\n        long long int pref[n];\n        long long int suf[n];\n\t\t\n\t\t//Calculating the prefix sum\n        pref[0]=nums[0];\n        for(int i=1;i<n;i++){\n            pref[i]=pref[i-1]+nums[i];\n        }\n\t\t\n\t\t//Calculating the suffix sum\n        suf[n-1]=nums[n-1];\n        for(int i=n-2;i>=0;i--){\n            suf[i]=suf[i+1]+nums[i];\n        }\n        int left[n];\n        int right[n];\n        stack<int> s;\n\t\t\n\t\t//Calculating the next smaller element on the right side\n        s.push(0);\n        for(int i=1;i<n;i++){\n            if(s.empty()){\n                s.push(i);\n            }else{\n                while(!s.empty()&&nums[s.top()]>nums[i]){\n                    right[s.top()]=i;\n                    s.pop();\n                }\n                s.push(i);\n            }\n        }\n        while(!s.empty()){\n            right[s.top()]=n;\n            s.pop();\n        }\n\t\t\n\t\t//Calculating the next smaller element on the left side\n        s.push(n-1);\n        for(int i=n-2;i>=0;i--){\n            if(s.empty()){\n                s.push(i);\n            }else{\n                while(!s.empty()&&nums[s.top()]>nums[i]){\n                    left[s.top()]=i;\n                    s.pop();\n                }\n                s.push(i);\n            }\n        }\n        while(!s.empty()){\n            left[s.top()]=-1;\n            s.pop();\n        }\n\t\t\n\t\t//Calculating the answer for each of the elements and storing the maximum of them\n        long long int ans=0;\n        for(int i=0;i<n;i++){\n            long long int l=0;\n            if(left[i]==-1){\n                l=pref[i];\n            }else{\n                l=pref[i]-pref[left[i]];\n            }\n            long long int r=0;\n            if(right[i]==n){\n                r=suf[i];\n            }else{\n                r=suf[i]-suf[right[i]];\n            }\n            ans=max(ans,(l+r-nums[i])*nums[i]*1ll);\n        }\n        return (ans)%mod;\n    }
['Stack', 'C']