C++ || Using Stack || finding next smaller and prev smaller of each element
Intuition: \n1.Next smaller and prev smaller will be used to get the range of the subarrays in which a particular element if occurs will always be minimum.\n2.P
**Intuition:** \n1.Next smaller and prev smaller will be used to get the range of the subarrays in which a particular element if occurs will always be minimum.\n2.Prefix sum will be used to get the sum of subarray using lr and rl arrays.\n3.At last the answer will be mx with mod 1e9+7.\n\nclass Solution {\npublic:\n\n    int maxSumMinProduct(vector<int>& nums) {\n        int n = nums.size();\n\t\t// lr stores next smaller of each element.\n\t\t// rl stores prev smaller of each element.\n\t\t// pre stores prefix sum of nums.\n\t\t// v is used to simulate as a stack.\n        vector<long long> lr(n, n), rl(n, -1), pre(n+1, 0), v;\n        \n\t\t// calculating next smaller of each element in nums and storing index in lr, using same for loop to find the prefix sum.\n        for(int i=0; i<n; ++i){\n            pre[i+1] = pre[i] + nums[i]; // calculating prefix sum array\n            while(!v.empty() and nums[i] < nums[v.back()]){\n                lr[v.back()] = i;\n                v.pop_back();\n            }\n            v.push_back(i);\n        }\n        \n        v.clear();\n        \n\t\t// calculating the prev smaller of each element of nums and storing index in rl\n        for(int i=n-1; i >= 0; --i){\n            while(!v.empty() and nums[i] < nums[v.back()]){\n                rl[v.back()] = i;\n                v.pop_back();\n            }\n            v.push_back(i);\n        }\n        \n        long long mx = 0, mod = 1e9+7;\n        \n        for(int i=0; i<n; ++i){\n            long long sum = pre[lr[i]] - pre[rl[i] + 1];\n            mx = max(mx, 1LL * nums[i] * sum);// multiplying with 1LL to convert the number to long long integer.\n        }\n        \n        return mx % mod;\n    }\n};\n\n**Time: O(N), Space: O(N)**\n**PLEASE UPVOTE IF HELPFUL!!!**\nFor doubt or query, comment below.\n\nSimilar Question: **Leetcode 84. Largest Rectangle in Histogram, just change the histogram width with sum.**
['Stack', 'C']