[C++] Segment tree approach with explanation O(n * log(n)) time
Intuition: We want to maximize the sumOfElements*minElement. minElement is the bottleneck element which decreases the sum. Idea is to compute it first for the e
Intuition: We want to maximize the sumOfElements*minElement. minElement is the bottleneck element which decreases the sum. Idea is to compute it first for the entire range of values. Then remove the min elment (which divides array in two parts - 0-> minIndex-1 and minIndex+1 -> n-1). We recur for both parts and keep updating the globalMax while doing this and return global max in the end.\n\nComplexity: O(n * log(n))\n- An element is getting removed each time, so n. \n- We find the min in the range each time which takes log(n) time if we\'ve segment tree. \n- Sum can easily be obtained in constant time by using prefix sum array.\n```\nclass Solution {\n    int stSize, n, mod = 1e9 + 7;\n    vector<int> st;\n    vector<long> preSum;\n    long globalMax=0;\n\n    int createSt(int idx, int low, int high, vector<int>& nums)\n    {\n        if (low == high)\n        {\n            return st[idx] = low; // store index and not value\n        }\n\n        int mid = low + (high - low) / 2;\n        int leftMinIdx = createSt(2 * idx + 1, low, mid, nums);\n        int rightMinIdx = createSt(2 * idx + 2, mid + 1, high, nums);\n\n        return st[idx] = nums[leftMinIdx] < nums[rightMinIdx] ? leftMinIdx : rightMinIdx;\n    }\n\n    int getMin(int idx, int low, int high, int qLow, int qHigh, vector<int>& nums)\n    {\n        if (qHigh < low || high < qLow)\n        {\n            return INT_MAX;\n        }\n\n        if (qLow <= low && high <= qHigh)\n        {\n            return st[idx];\n        }\n\n        int mid = low + (high - low) / 2;\n        int leftMinIdx = getMin(2 * idx + 1, low, mid, qLow, qHigh, nums);\n        int rightMinIdx = getMin(2 * idx + 2, mid + 1, high, qLow, qHigh, nums);\n\n        if (leftMinIdx == INT_MAX)\n            return rightMinIdx;\n        else if (rightMinIdx == INT_MAX)\n            return leftMinIdx;\n        else\n            return nums[leftMinIdx] < nums[rightMinIdx] ? leftMinIdx : rightMinIdx;\n    }\n\n    void helper(int low, int high, vector<int>& nums)\n    {\n        if (low > high)\n        {\n            return;\n        }\n\n        int minIdx = getMin(0, 0, nums.size() - 1, low, high, nums);\n        globalMax = max(globalMax, nums[minIdx] * (preSum[high + 1] - preSum[low]));\n\n        helper(low, minIdx - 1, nums);\n        helper(minIdx + 1, high, nums);\n    }\n\npublic:\n    int maxSumMinProduct(vector<int>& nums)\n    {\n        n = nums.size();\n        int power = ceil(log2(n));\n        stSize = 2 * pow(2, power)-1;\n        st.resize(stSize, INT_MAX);\n\n        createSt(0, 0, n - 1, nums);\n\n        preSum.resize(n + 1, 0);\n\n        for (int i = 0; i < nums.size(); i++)\n        {\n            preSum[i + 1] = preSum[i] + nums[i];\n        }\n\n        helper(0, n - 1, nums);\n        return globalMax%mod;\n    }\n};\n```
[]