C++ Stack concept O(n)
The problem here is diverting from the actual problem. \nLet us consider each element in the nums array as the smallest element in their corresponding subarray.
The problem here is diverting from the actual problem. \nLet us consider each element in the nums array as the smallest element in their corresponding subarray. Now the problem reduces to finding the corresponding subarray for  each element. \nTo find each corresponding element we will use stack.\nStore the index of next smaller element in the left direction of current element in left array.\nSimilary do this for right array i.e. next smaller element in the right direction of current element.\nUsing left and right array we can find window/subarray for each element.\nNow we will apply this window on prefix sum array to compute the sum of each window in O(1) time.\n\nfor each element, the min-product would be, (prefixSum[right[i]] - prefixSum[left[i]+1) * nums[i]\n\n```\nint maxSumMinProduct(vector<int>& nums) {\n        vector<long>preSum, left(nums.size(),-1), right(nums.size(),nums.size());\n        preSum.push_back(0);\n        for(int i=0; i<nums.size(); i++)\n            preSum.push_back(preSum.back()+nums[i]);\n        \n        stack<int>st;\n        for(int i=0; i<nums.size(); i++){\n            while(!st.empty() && nums[i]<=nums[st.top()])\n                st.pop();\n            if(!st.empty())\n                left[i]=st.top();\n            st.push(i);\n        }\n        st = stack<int>();\n        for(int i=nums.size()-1; i>=0; i--){\n            while(!st.empty() && nums[i]<=nums[st.top()])\n                st.pop();\n            if(!st.empty())\n                right[i]=st.top();\n            st.push(i);\n        }\n        \n        long ans=0, mod=1e9+7;\n        \n        for(int i=0; i<nums.size(); i++){\n            long t=(preSum[right[i]]-preSum[left[i]+1])*nums[i];\n            ans=max(ans,t);\n        }\n        \n        return ans%mod;\n    }\n```
['Stack', 'C', 'Prefix Sum']