C++ Stack Solution using Nearest Smaller Element (Explained)
Basic idea:\n\nThe subarray where nums[i] will be minimum will be from (left[i], right[i]) both exclusive.\n\nExample: 3,1,5,6,4,2\nThe index of nearest element
**Basic idea:**\n\nThe subarray where nums[i] will be minimum will be from (left[i], right[i]) both **exclusive.**\n\nExample: 3,1,5,6,4,2\nThe index of nearest elements to the left (left array) (-1, if no smaller element to the right)\n[-1,-1,1,2,1,1]\nThe index of nearest elements to the right (right array) (n, if no smaller element to the right)\n[1,6,4,4,5,6]\n\nThe subarray where nums[4] will be minimum will be from (left[4] - right[4]), which is (1,5) which is[5,6,4]\nSimilarly, the subarray where nums[1]  is minimum will be (left[1] - right[1]), which is (-1,6) which is [3,1,5,6,4,2]\n\nSo for each item in the nums, we find the minProduct for the subarray which contains nums[i] as the minimum.\nWe do that by multiplying nums[i] with the sum of the subarray.\n\nThe answer will be the maximum of such minProducts.\n\n### **Code:**\n```\ntypedef long long ll;\nclass Solution {\n   public:\n    // get sum of subarray using prefix sum array\n    ll getSumRange(vector<ll>& vec, int l, int r) {\n        if (l == -1) return vec[r - 1];\n        return vec[r - 1] - vec[l];\n    }\n    int maxSumMinProduct(vector<int>& nums) {\n        int n = nums.size();\n        stack<int> s;\n        //find index of nearest smaller element to the left\n        vector<int> left(n, -1);\n        for (int i = 0; i < n; i++) {\n            while (!s.empty() && nums[s.top()] >= nums[i]) {\n                s.pop();\n            }\n            if (!s.empty())\n                left[i] = s.top();\n            s.push(i);\n        }\n        //clear stack\n        while (!s.empty()) s.pop();\n        //find index of nearest smaller element to the right\n        vector<int> right(n, n);\n        for (int i = n - 1; i >= 0; i--) {\n            while (!s.empty() && nums[s.top()] >= nums[i]) {\n                s.pop();\n            }\n            if (!s.empty())\n                right[i] = s.top();\n            s.push(i);\n        }\n        //generate prefix array\n        vector<ll> prefix(n);\n        for (int i = 0; i < n; i++)\n            if (i == 0)\n                prefix[i] = nums[i];\n            else\n                prefix[i] = nums[i] + prefix[i - 1];\n        //generate answer\n        ll ans = 0;\n        for (int i = 0; i < n; i++) {\n            ll val = (ll)nums[i] * (ll)(getSumRange(prefix, left[i], right[i]));\n            ans = max(ans, val);\n        }\n        return int(ans % int(1e9 + 7));\n    }\n};\n```
[]