C++ | Faster than 100%
Memory Can be reduced by not using rightMin array but below code is more intuitive :\n\nclass Solution\n{\npublic:\n    #define mod 1000000007\n    vector<int> 
Memory Can be reduced by not using rightMin array but below code is more intuitive :\n```\nclass Solution\n{\npublic:\n    #define mod 1000000007\n    vector<int> findLeftMinimum(vector<int> &a, int &n)\n    {\n        vector<int> leftMin(n + 1, 0);\n        stack<int> s;\n        for (int i = 1; i <= n; i++)\n        {\n            while (!s.empty() && a[s.top()] >= a[i])\n            {\n                s.pop();\n            }\n            if (s.empty())\n                leftMin[i] = 0;\n            else\n                leftMin[i] = s.top();\n            s.push(i);\n        }\n        return leftMin;\n    }\n    vector<int> findRightMinimum(vector<int> &a, int &n)\n    {\n        vector<int> rightMin(n + 1, 0);\n        stack<int> s;\n        for (int i = n; i >= 1; i--)\n        {\n            while (!s.empty() && a[s.top()] >= a[i])\n            {\n                s.pop();\n            }\n            if (s.empty())\n                rightMin[i] = n + 1;\n            else\n                rightMin[i] = s.top();\n            s.push(i);\n        }\n        return rightMin;\n    }\n    long long give(vector<long long> &pref, int &l, int &r)\n    {\n        return pref[r] - pref[l - 1];\n    }\n    int maxSumMinProduct(vector<int> &nums)\n    {\n        int n = nums.size();\n        nums.insert(nums.begin(), -1);  //To make the array 1-based\n        vector<int> r = findRightMinimum(nums, n);\n        vector<int> l = findLeftMinimum(nums, n);\n        vector<long long> pref(n + 1, 0);\n        for (int i = 1; i <= n; i++)\n            pref[i] = pref[i - 1] + nums[i];\n        \n        long long ans = 0;\n        for (int i = 1; i <= n; i++)\n        {\n            int left = l[i];\n            int right = r[i];\n            left++;\n            right--;\n            ans = max(ans, nums[i] * give(pref, left, right));\n        }\n        return ans % mod;\n    }\n};\n```\n![image](https://assets.leetcode.com/users/images/6752cac5-0d0d-4f1d-b6bf-d947d886edfc_1620583014.7801464.png)\n
[]