✅✅Faster || Easy To Understand || C++ Code
Using Stack && Prefix Sum\n\n Time Complexity :- O(N)\n\n Space Complexity :- O(N)\n\n\nclass Solution {\npublic:\n    int maxSumMinProduct(vector<int>& arr) {\
* ***Using Stack && Prefix Sum***\n\n* ***Time Complexity :- O(N)***\n\n* ***Space Complexity :- O(N)***\n\n```\nclass Solution {\npublic:\n    int maxSumMinProduct(vector<int>& arr) {\n        \n        int n = arr.size();\n        \n        long long mod = 1e9 + 7;\n        \n        // find the prefix sum\n        \n        vector<long long> prefix(n, 0);\n        \n        prefix[0] = arr[0];\n        \n        for(int i = 1; i < n; i++)\n        {\n            prefix[i] = prefix[i - 1] + arr[i];\n        }\n        \n        // declare a stack\n        \n        stack<int> st;\n        \n        // find the index of next smaller element on left side\n        \n        vector<int> left(n, -1);\n        \n        vector<int> right(n, n);\n        \n        for(int i = 0; i < n; i++)\n        {\n            while(st.empty() == false && arr[st.top()] >= arr[i])\n            {\n                st.pop();\n            }\n            \n            if(st.empty())\n            {\n                left[i] = -1;\n            }\n            else\n            {\n                left[i] = st.top();\n            }\n            \n            st.push(i);\n        }\n        \n        // empty stack\n        \n        while(st.empty() == false)\n        {\n            st.pop();\n        }\n        \n        // find the next smaller element on right side\n        \n        for(int i = n - 1; i >= 0; i--)\n        {\n            while(st.empty() == false && arr[st.top()] >= arr[i])\n            {\n                st.pop();\n            }\n            \n            if(st.empty())\n            {\n                right[i] = n;\n            }\n            else\n            {\n                right[i] = st.top();\n            }\n            \n            st.push(i);\n        }\n        \n        // calculate maximum min-product \n       \n        long long max_sum = 0;\n        \n        for(int i = 0; i < n; i++)\n        {\n            long long sum = 0;\n            \n            sum += prefix[right[i] - 1];\n            \n            if(left[i] >= 0)\n            {\n                sum -= prefix[left[i]];\n            }\n            \n            sum *= arr[i];\n            \n            max_sum = max(max_sum, sum);\n        }\n        \n        return max_sum % mod;\n    }\n};\n```
['Stack', 'C', 'Monotonic Stack', 'Prefix Sum', 'C++']