看leetcode上的题解都是DP，分享一下分治的做法

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        return merge(nums, 0, n - 1);
    }
    int merge(vector<int>& nums, int l, int r) {
        if (l >= r) return nums[l];
        int mid = l + r >> 1;
        int res = max(merge(nums, l, mid), merge(nums, mid + 1, r)); 
        int leftPos, leftNeg, rightPos, rightNeg;
        leftPos = rightPos = 0;
        leftNeg = rightNeg = 0;
        for (int i = mid + 1, s = 1; i <= r; i++) {
            s *= nums[i];
            if (s > rightPos) rightPos = s;
            if (s < rightNeg) rightNeg = s;
        }
        for (int i = mid, s = 1; i >= l; i--) {
            s *= nums[i];
            if (s > leftPos) leftPos = s;
            if (s < leftNeg) leftNeg = s;
        }
        return max(res, max(leftNeg * rightNeg, leftPos * rightPos));
    }
};