Not the most most efficient but very intuitive approach.
Intuition\nMin of the subarray effects the product the most, since all the nums are greater >= 1.\nIf minValue is part of the maximum product subarray. \nThen t
# Intuition\nMin of the subarray effects the product the most, since all the nums are greater >= 1.\nIf minValue is part of the maximum product subarray. \nThen that product = minValue*(sum of whole array).\nOtherwise it\'s either the left subarray or the right subarray.\n\n\n# Approach\nDivide and Conquer strategy with Segment Tree for minValue range query in the given subarray.\n\nWe store the minValue along with the index in the tree so that we can use it to split the array recursively and compare the two halves with the whole array that includes the minValue.\n\nWe return the max of the three products here (the left subarray, the right subarray and the whole array).\n\n\n# Complexity\n- Time complexity:\nI don\'t think I have the time complexity right here.\nO(nlog(n)) for the divide and conquer. But we are doing O(log(n)) query for the range minimum. \nTherefore, it should be worse than O(nlog(n)). May be O(nlog(n)*log(n))\n\n- Space complexity:\nO(n) for prefixSum\nO(4*n) ~ O(n) for segmentTree\n\n# Code\n```\n#define mod 1000000007\n\nclass SegmentTree {\n    private:\n    vector<pair<int, int>> tree;\n    vector<int> lo, hi;\n    int n;\n\n    public:\n    SegmentTree(int size) {\n        this->n = size;\n        tree.resize(n << 2);\n        lo.resize(n << 2, 0);\n        hi.resize(n << 2, 0);\n\n        init(1, 0, n - 1);\n    }\n\n    void update(int i) {\n        if(tree[i << 1].first < tree[i << 1 | 1].first)\n            tree[i] = make_pair(tree[i << 1].first, tree[i << 1].second);\n        else\n            tree[i] = make_pair(tree[i << 1 | 1].first, tree[i << 1 | 1].second);\n    }\n\n    void build(vector<int>& nums) {\n        construct(1, 0, n -1, nums);\n    }\n\n    pair<int, int> construct(int i, int a, int b, vector<int>& nums) {\n        if(a == b) {\n            tree[i] = make_pair(nums[a], a);\n            return tree[i];\n        }\n        int m = (a + b) / 2;\n        pair<int, int> pl = construct(i << 1, a, m, nums);\n        pair<int, int> pr = construct(i << 1 | 1, m + 1, b, nums);\n        update(i);\n        if(pl.first < pr.first)\n            return pl;\n        return pr;\n    }\n\n    void init(int i, int a, int b) {\n        lo[i] = a;\n        hi[i] = b;\n\n        if(a == b)\n            return;\n        int m = (a + b) / 2;\n        init(i << 1, a, m);\n        init(i << 1 | 1, m + 1, b);\n    }\n\n\n    pair<int, int> rmq(int i, int a, int b) {\n        if(b < lo[i] || hi[i] < a)\n            return make_pair(INT_MAX, -1);\n        if(a <= lo[i] && hi[i] <= b) {\n            return tree[i];\n        }\n        pair<int, int> pl = rmq(i << 1, a, b); \n        pair<int, int> pr = rmq(i << 1 | 1, a , b);\n        update(i);\n        if(pl.first < pr.first)\n            return pl;\n        return pr;\n    }\n\n    pair<int, int> rangeQuery(int l, int r) {\n        return rmq(1, l, r);\n    }\n\n    void printTree() {\n        for(int i = 0; i < n << 1; i++) {\n            cout << tree[i].first << ":" << tree[i].second <<  "\\t";\n        }\n        cout << endl;\n    }\n\n\n};\n\nclass Solution {\npublic:\n\n    long long divideAndConquer(SegmentTree* tree, vector<int>& nums, vector<long long>& prefixSum, int l, int r) {\n        if(l > r)\n            return -1;\n        if(l == r) {\n            long long num = nums[l];\n            return (num *num);\n        }\n\n        pair<int, int> p = tree->rangeQuery(l, r);\n\n        long long left = divideAndConquer(tree, nums, prefixSum, l, p.second - 1);\n        long long right = divideAndConquer(tree, nums, prefixSum, p.second + 1, r);\n        long long withMin = (prefixSum[r] - prefixSum[l] + (long long)nums[l])*p.first;\n        return max(withMin, max(left, right));\n    }\n\n    int maxSumMinProduct(vector<int>& nums) {\n        int n = nums.size();\n\n        vector<long long> prefixSum(n, 0);\n        prefixSum[0] = nums[0];\n        SegmentTree* tree = new SegmentTree(nums.size());\n        tree->build(nums);\n\n        for(int i = 1; i < n; i++) {\n            prefixSum[i] = prefixSum[i - 1] + nums[i];\n        }\n        return divideAndConquer(tree, nums, prefixSum, 0, n - 1) % mod;\n    }\n};\n```
['Divide and Conquer', 'Segment Tree', 'C++']