C++ Stack Solution
\nvector<long long> prefixSum(vector<int> &nums, int n)\n{\n\tvector<long long> prefix;\n\n\tlong long sum = 0;\n\n\tfor(auto &x : nums)\n\t{\n\t\tsum += x;\n\t
```\nvector<long long> prefixSum(vector<int> &nums, int n)\n{\n\tvector<long long> prefix;\n\n\tlong long sum = 0;\n\n\tfor(auto &x : nums)\n\t{\n\t\tsum += x;\n\t\tprefix.push_back(sum);\n\t}\n\n\treturn prefix;\n}\n\nvector<int> nsl(vector<int> &nums, int n)\n{\n\tstack<int> st;\n\n\tvector<int> vect;\n\n\tfor(int i = 0; i < n; i++)\n\t{\n\t\twhile(!st.empty() and nums[i] <= nums[st.top()])\n\t\t\tst.pop();\n\n\t\tst.empty() ? vect.push_back(0) : vect.push_back(st.top() + 1);\n\n\t\tst.push(i);\n\t}\n\n\treturn vect;\n}\n\nvector<int> nsr(vector<int> &nums, int n)\n{\n\tstack<int> st;\n\n\tvector<int> vect;\n\n\tfor(int i = n-1; i >= 0; i--)\n\t{\n\t\twhile(!st.empty() and nums[i] <= nums[st.top()])\n\t\t\tst.pop();\n\n\t\tst.empty() ? vect.push_back(n-1) : vect.push_back(st.top()-1);\n\n\t\tst.push(i);\n\t}\n\n\treverse(vect.begin(), vect.end());\n\n\treturn vect;\n}\n\nlong long getSum(vector<long long> &prefix, int l, int r)\n{\n\tif(l == 0)\n\t\treturn prefix[r];\n\n\treturn prefix[r] - prefix[l-1];\n}\n\nint maxSumMinProduct(vector<int>& nums) {\n\n\tint n = nums.size(), mod = 1e9+7;\n\n\tvector<int> left = nsl(nums, n), right = nsr(nums, n); // nearest smaller to left and right respectively/\n\n\tvector<long long> prefix = prefixSum(nums, n);\n\n\tlong long maxProduct = INT_MIN, temp;\n\n\tfor(int i = 0;i < n; i++)\n\t{\n\t\ttemp = ((long long)nums[i] * getSum(prefix, left[i], right[i]));\n\t\tmaxProduct = max(maxProduct, temp);\n\t}\n\n\treturn maxProduct % mod;\n}\n```\n\nTime Complexity - `O(n)`\nSpace Complexity - `O(n)`
['Stack', 'Prefix Sum']