c++ Monotone Stack
Classical variation of Monotonic stack \n\nEXPLANATION : \n\n\n\nFunction definition\n \n \n C++\n #define ll long long \nclass Solution {\npublic:\n    int max
Classical variation of Monotonic stack \n\n**EXPLANATION** : \n\n\n<details>\n<summary>Function definition</summary>\n <pre>\n \n ```C++\n #define ll long long \nclass Solution {\npublic:\n    int maxSumMinProduct(nums) {        \n        ll prefix[100000+1]{0};\n        ll suffix[100000+1]{0};        \n        ll n = nums.size();\n        unordered_map<ll,ll> minL,minR;        \n        stack<ll>st,st2; //to store indices, no need of stack of pairs \n\t\tlong long sum = 0 , ans = 0;\n        }\n```\n</pre>\n</details>\n<br>\n<details>\n<summary>Prefix sum </summary>\n <pre>\n \n```C++\nfor(ll i=0;;+i){\n            prefix[i] = nums[i];\n            if(i-1 >= 0)prefix[i] += prefix[i-1];\n\tif(i>=n)break;\n        }\n```\t\n</pre>\n</details>\n<br>\n<details>\n<summary>suffix sum </summary>\n <pre> \n \n ```C++\n for(ll i=n-1;i>=0;--i){\n            suffix[i] = nums[i];\n            if(n > i+1)suffix[i] += suffix[i+1];\n        }\n```\n</pre>\n</details>\n<br>\n<details>\n<summary>Find Previous minimum index for each of the current index </summary>\n <pre>  \n \n ```C++\n for(int i=n-1;i>=0;--i){\n            while(!st.empty() and nums[st.top()] >= nums[i])\n                st.pop();\n            if(!st.empty() and nums[i] > nums[st.top()] )\n                minR[i] = st.top();\n            st.push(i);\n        }\n```\n</pre>\n</details>\n<br>\n<details>\n<summary>Find Next minimum index for each of the current index </summary>\n <pre>    \n \n ```C++\n for(int i=0;n>i;++i){\n            while(!st2.empty() and nums[st2.top()] >= nums[i])\n                st2.pop();\n            if(!st2.empty() and nums[i] > nums[st2.top()] )\n                minL[i] = st2.top();\n            st2.push(i);\n        }  \n```\n</pre>\n</details>\n  <br>\n<details>\n<summary>Find by considering each element as the smallest element  </summary>\n <pre>     \n \n ```C++\n for(int i=0;n>i;++i){                        \n          long long val = prefix[i] + suffix[i] - nums[i];            \n          if(minL.count(i))\n              val -= prefix[minL[i]];\n          if(minR.count(i))\n              val -= suffix[minR[i]];                          \n          val *= nums[i];                        \n          ans = max(ans,val);            \n      } \n```\t  \n</pre>\n</details>\n   <br>\n<details>\n<summary>Modding out </summary>\n <pre>   \n \n ```C++\n        int mod = 1e9+7;\n        return ans%mod;\n    } \n```\t\n</pre>\n</details>\n      \n\n\n\n**Actual code**\n```\n#define ll long long \nclass Solution {\npublic:\n    int maxSumMinProduct(vector<int>& nums) {\n        \n        ll prefix[100000+1]{0};\n        ll suffix[100000+1]{0};        \n        ll n = nums.size();\n        unordered_map<ll,ll> minL,minR;        \n        stack<ll>st,st2; //to store indices, no need of stack of pairs \n\t\tlong long sum = 0 , ans = 0;\n```\t\n\n```\n\t\t//prefix sum\n        for(ll i=0;i<n;++i){\n            prefix[i] = nums[i];\n            if(i-1 >= 0)prefix[i] += prefix[i-1];\n        }\n```\n\n```\n\t\t//suffix sum\n        for(ll i=n-1;i>=0;--i){\n            suffix[i] = nums[i];\n            if(i+1 < n)suffix[i] += suffix[i+1];\n        }\n```\n```\n\t\t//find left minimum index for each of the present index \n        for(int i=n-1;i>=0;--i){\n            while(!st.empty() and nums[st.top()] >= nums[i])\n                st.pop();\n            if(!st.empty() and nums[st.top()] < nums[i])\n                minR[i] = st.top();\n            st.push(i);\n        }\n```      \n\n\n```\n\t//find right minimum index for each of the present index \n        for(int i=0;i<n;++i){\n            while(!st2.empty() and nums[st2.top()] >= nums[i])\n                st2.pop();\n            if(!st2.empty() and nums[st2.top()] < nums[i])\n                minL[i] = st2.top();\n            st2.push(i);\n        }      \n  ```\n  \n  \n  \n  ```\n\t\t//find the answer by considering each element as the smallest element and\n\t\t//including the maximum length array from left and right \n\t\t\n\t\t\n        for(int i=0;i<n;++i){                        \n            long long val = prefix[i] + suffix[i] - nums[i];            \n            if(minL.count(i))\n                val -= prefix[minL[i]];\n            if(minR.count(i))\n                val -= suffix[minR[i]];                          \n            val *= nums[i];                        \n            ans = max(ans,val);            \n        }\n```\n\n\n        int mod = 1e9+7;\n        return ans%mod;\n    }\n};\n
['C', 'Monotonic Stack', 'C++']