✅ [C++] Intuitive Prefix Sum Array and Monotonic Stack
This problem has a direct intuition. We observe that if we consider each number as a minimum of some subarray, we just need to find that subarray. Now, the ques
This problem has a direct intuition. We observe that if we consider each number as a minimum of some subarray, we just need to find that subarray. Now, the question is \n**How to find that subarray?** \nWe just need to use the fact that our current element is the minimum element in that subarray. That means that on both, to its left and to its right, we should have numbers which are greater than or equal to this current number. For ex, \n```\nnums[] = [1,2,3,3,4,5,3,2]\n```\nFor i = 3, the subarray possible is, [3,3,4,5,3], since beyond these boundaries, we will have numbers which are smaller than 3, which, if included, will change the minimum of this subarray. \n**Therefore, the problem reduces to finding the previous smaller and next smaller element.**\nFor that, we use **`monotonic stack`**. If you dont know about monotonic stack, it is a way of using stack in such a way that it finds the next smaller element in an array. \nFor the sum of a subarray, I used **prefix sum array**. \n\nRest can be seen from the code below :)\n\n```\nclass Solution {\npublic:\n    int maxSumMinProduct(vector<int>& nums) {\n        long long n = nums.size(), sum = 0;\n        vector<long long> prefix(n,0);\n\t\t\n\t\t// Prefix sum array to find the sum of any subarray in O(1)\n        for(int i = 0; i<nums.size(); i++){\n            sum += nums[i];\n            prefix[i] = sum;\n        }\n        \n        vector <int> prev(n,0), next(n,0);\n        \n\t\t// Finding the previous smaller element\n        stack <pair<int,int>> s;\n        for(int i = 0; i<n; i++){\n            if(s.empty()) s.push({nums[i],i});\n            else{\n                while(!s.empty() and nums[i]<s.top().first) next[s.top().second] = i, s.pop();\n                s.push({nums[i],i});\n             }\n        }\n        while(!s.empty()) next[s.top().second] = n, s.pop();\n        \n\t\t// Finding the next smaller element\n        for(int i = n-1; i>=0; i--){\n            if(s.empty()) s.push({nums[i],i});\n            else{\n                while(!s.empty() and nums[i]<s.top().first) prev[s.top().second] = i, s.pop();\n                s.push({nums[i],i});\n            }\n        }\n        while(!s.empty()) prev[s.top().second] = 0, s.pop();\n        \n\t\t// Calculating the answer from prefix array, previous and next smaller array\n        long long ans = 0;\n        for(int i = 0; i<n; i++){\n\t\t\tlong long prod = prefix[next[i]-1];\n\t\t\t\n\t\t\t// If current element has no previous smaller element.\n            if(nums[prev[i]]<nums[i]) prod -= prefix[prev[i]];\n            prod *= nums[i];\n            ans = max(ans,prod);\n        }\n        return ans%1000000007;\n    }\n};\n```
['Stack', 'C', 'Monotonic Stack', 'Prefix Sum']