O(N) prefix sum and monotonic stack approach - C++
\nstatic int speedUp=[](){\n    std::ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return 0;\n}();\n\n\nclass Solution {\npub
```\nstatic int speedUp=[](){\n    std::ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return 0;\n}();\n\n\nclass Solution {\npublic:\n    int mod = 1e9 + 7 ; \n    vector<int> evalLeft(vector<int>& arr) // Evaluate previous smaller element for every index i \n    {\n        stack<pair<int, int>> st ;\n        vector<int> left ; \n        for(int i = 0; i < arr.size(); i++)\n        {\n            if (st.empty() == true)\n                left.push_back(-1) ;\n            else \n            {\n                while(st.empty() == false && st.top().first >= arr[i]) \n                    st.pop() ; \n                if (st.empty() == true)\n                    left.push_back(-1) ;\n                else \n                    left.push_back(st.top().second) ; \n            }\n            st.push({arr[i], i}) ; \n        } \n        return left ; \n    }\n    vector<int> evalRight(vector<int>& arr) // Evaluate next smaller element for every index i \n    {\n        stack<pair<int, int>> st ;\n        vector<int> right ;\n        for(int i = arr.size()-1; i >=0 ; i--)\n        {\n            if (st.empty() == true)\n                right.push_back(-1) ;\n            else \n            {\n                while(st.empty() == false && st.top().first >= arr[i]) \n                    st.pop() ;\n                if (st.empty() == true)\n                    right.push_back(-1) ;\n                else \n                    right.push_back(st.top().second) ; \n            }\n            st.push({arr[i], i}) ;\n        }\n        reverse(right.begin(), right.end()) ;\n        return right ; \n    }\n    int maxSumMinProduct(vector<int>& arr) {\n        int n = arr.size() ;\n        vector<int> left = evalLeft(arr) ;\n        vector<int> right = evalRight(arr) ;\n        vector<long long> prefix(n) ; \n        prefix[0] = arr[0] ;\n        for(int i = 1; i < n; i++) // Compute prefix sum \n            prefix[i] = prefix[i-1] + arr[i] ; \n        long long ans = 0 ; \n        for(int i = 0; i < n; i++)\n        {\n            long long sum = 0 ; \n\t\t\t// Assuming curr element / index to be i \n            // Obtaining left sum \n\t\t\tif (left[i] == -1) \n                sum += prefix[i] ;\n            else \n                sum += prefix[i] - prefix[left[i]] ;\n\t\t\t// Obtaining right sum \n            if (right[i] == -1){\n                if (i != 0)\n                    sum += prefix[n-1] - prefix[i-1] ; \n                else \n                    sum += prefix[n-1] ; \n            }\n            else \n            {\n                if (i != 0)\n                    sum += prefix[right[i]-1] - prefix[i-1] ; \n                else \n                    sum += prefix[right[i]-1] ; \n            }\n\t\t\t// arr[i] added twice, subtract it once \n            sum -= arr[i] ; \n            ans = max(ans, sum*arr[i]) ;\n        }\n        return ans % mod ; \n    }\n};\n```
['Stack', 'C', 'Monotonic Stack', 'Prefix Sum']