C++ Solution. start from the smallest number. Greedy.
\n### Idea\n- We start from the smallest number and find the left and right bound by the current index, then the answer is current_number * (prefix[r] - prefix[
\n### Idea\n- We start from the smallest number and find the left and right bound by the current index, then the answer is current_number * (prefix[r] - prefix[l]).\n\n\n### Time Complexity\n- Time O(nLogn)\n- Space O(n)\n\n### Solution\n- C++\n```\nclass Solution {\npublic:\n    long long M = 1e9 + 7;\n    int maxSumMinProduct(vector<int>& nums) {\n        map<long long, long long> stick;\n        vector<pair<int, int> > sortedArray(nums.size());\n        vector<long long> prefix = {nums[0]};\n        for(int i = 0; i < nums.size(); i++) {\n            sortedArray[i] = {nums[i], i};\n        }\n        for(int i = 1; i < nums.size(); i++) {\n            prefix.push_back(prefix.back() + (long long)nums[i]);\n        }\n        sort(sortedArray.begin(), sortedArray.end());\n        long long ans = 0;\n        for(auto [num, i] : sortedArray) {\n            auto it = stick.lower_bound(i);\n            int r = nums.size(); //right bound\n            if(it != stick.end()) r = it->first;\n            int l = -1;\n            if(it != stick.begin()) {//left bound\n                --it;\n                l = it->first;\n            }\n            long long cur = (long long)num * (long long)(prefix[r - 1] - (l >= 0 ? prefix[l] : 0));\n            ans = max(ans, cur);\n            stick[i] = 1;\n        }\n        return ans % M;\n    }\n};\n```
[]