[Python] Divide-and-conquer O(nlogn)
\nclass Solution:\n    def maxSumMinProduct(self, nums: List[int]) -> int:\n        def maxSumMinProductRange(i, j):\n            if i == j:\n                re
```\nclass Solution:\n    def maxSumMinProduct(self, nums: List[int]) -> int:\n        def maxSumMinProductRange(i, j):\n            if i == j:\n                return nums[i]*nums[i]\n            mid = i + (j - i)//2\n            p1 = mid\n            p2 = mid + 1\n            cur_min = min(nums[p1], nums[p2])\n            cur_sum = nums[p1] + nums[p2]\n            max_so_far = cur_min*cur_sum\n            while p1 > i or p2 < j:\n                if p1 == i or (p2 < j and nums[p2 + 1] >= nums[p1 - 1]):\n                    p2 += 1\n                    cur_min = min(cur_min, nums[p2])\n                    cur_sum += nums[p2]\n                else:\n                    p1 -= 1\n                    cur_min = min(cur_min, nums[p1])\n                    cur_sum += nums[p1]\n                max_so_far = max(max_so_far, cur_min*cur_sum)\n            left = maxSumMinProductRange(i, mid)\n            right = maxSumMinProductRange(mid + 1, j)\n            return max(left, right, max_so_far)\n        return maxSumMinProductRange(0, len(nums) - 1) % int(1e9 + 7)\n```
['Divide and Conquer', 'Python']