C++ O(n*log(n)) greedy by pre sum and balanced tree
Product = min * sum. We can get max product for each min by finding max sum.\nGreedily iterate min ascendingly, use a balanced tree to maintain the visited mins
Product = min * sum. We can get max product for each min by finding max sum.\nGreedily iterate min ascendingly, use a balanced tree to maintain the visited mins. So the max sum for each min is the longest adjacent uninterrupted segment which can be find in O(log(n)) using the balanced tree.\nAlso calculate pre sum in advance to get the sum of intervals.\n```\nclass Solution {\npublic:\n    int maxSumMinProduct(vector<int>& nums) {\n        constexpr int mod = 1e9 + 7;\n        int n = nums.size();\n        vector<long long int> preSum(nums.size() + 1);\n        preSum[0] = 0;\n        vector<pair<int, int>> list(nums.size());\n        for (int i = 0; i < n; i++) {\n            preSum[i + 1] = preSum[i] + nums[i];\n            list[i].first = nums[i];\n            list[i].second = i;\n        }\n        sort(list.begin(), list.end());\n        set<int> tree;\n        tree.insert(-1);\n        tree.insert(n);\n        long long int result = 0;\n        for (int i = 0; i < n; i++) {\n            set<int>::iterator it = tree.upper_bound(list[i].second);\n            long long int sum = preSum[*it] - preSum[*prev(it) + 1];\n            result = max(result, list[i].first * sum);\n            tree.insert(list[i].second);\n        }\n        return result % mod;\n    }\n};\n```\n\nActually my first intuition is divide and conquer. But the input data can be unbalanced which degrades algorithm to O(n^2) in worst case.\nWorth mention, though.\n```\n// TLE\nclass Solution {\n    long long int find(const vector<int> &nums, int start, int end) {\n        if (start == end) {\n            return 0;\n        }\n        long long int minVal = INT_MAX, sum = 0;\n        int minIdx;\n        for (int i = start; i < end; i++) {\n            sum += nums[i];\n            if (nums[i] < minVal) {\n                minVal = nums[i];\n                minIdx = i;\n            }\n        }\n        long long int result = minVal * sum;\n        result = max(result, find(nums, start, minIdx));\n        result = max(result, find(nums, minIdx + 1, end));\n        return result;\n    }\npublic:\n    int maxSumMinProduct(vector<int>& nums) {\n        int mod = 1e9 + 7;\n        return find(nums, 0, nums.size()) % mod;\n    }\n};\n```
[]