分治法

一、递归

边界条件和递归体

二、分治法基本思想

1. 将规模为n的问题分解为k个子问题，这些子问题相互独立且与原问题相同
2. 递归纵深时拆分问题，逐层返回是归并计算。

三、步骤

1. 分解
2. 求解
3. 合并

四、典型实例

1. 归并排序

    //两路归并算法，两个排好序的子序列合并为一个子序列
    public void merge(int []a,int left,int mid,int right){
        int []tmp=new int[a.length];//辅助数组
        int p1=left,p2=mid+1,k=left;//p1、p2是检测指针，k是存放指针

        while(p1<=mid && p2<=right){
            if(a[p1]<=a[p2])
                tmp[k++]=a[p1++];
            else
                tmp[k++]=a[p2++];
        }

        while(p1<=mid) tmp[k++]=a[p1++];//如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
        while(p2<=right) tmp[k++]=a[p2++];//同上

        //复制回原数组
        for (int i = left; i <=right; i++) 
            a[i]=tmp[i];
    }

    public void mergeSort(int [] a,int start,int end){
        if(start<end){//当子序列中只有一个元素时结束递归
            int mid=(start+end)/2;//划分子序列
            mergeSort(a, start, mid);//对左侧子序列进行递归排序
            mergeSort(a, mid+1, end);//对右侧子序列进行递归排序
            merge(a, start, mid, end);//合并
        }
    }

2. 最大子段和

    int max3(int a, int b, int c)           // 求三个数的最大值
    {
        int max = a;
        if (b > max)
            max = b;
        if (c > max)
            max = c;
        return max;
    }

    int MaxSubsequenceSum(int array[], int left, int right)
    {
        if (left == right)          // 设置基准，即递归终止条件
            return array[left];

        int middle = (left + right) / 2;

        int leftMaxSubsequenceSum = MaxSubsequenceSum(array, left, middle);     // 求左半部分最大子序列和
        int rightMaxSubsquenceSum = MaxSubsequenceSum(array, middle + 1, right);    // 求右半部分最大子序列和

        // 处理左右边界问题：最大子序列跨越中间，包含左半部分最右一个数，同时包含右半部分最左一个数
        int maxLeftBorderSum = 0;
        int maxRightBorderSum = 0;
        int tempSum = 0;        // 临时求和变量
        for (int i = middle; i >= left; i--)
        {
            tempSum += array[i];
            if (tempSum > maxLeftBorderSum)
                maxLeftBorderSum = tempSum;     // 左边包含边界最大序列和
        }
        tempSum = 0;
        for (int i = middle + 1; i < right; i++)
        {
            tempSum += array[i];
            if (tempSum > maxRightBorderSum)
                maxRightBorderSum = tempSum;    // 右边包含边界最大序列和
        }

        int maxBorderSum = maxRightBorderSum + maxLeftBorderSum;        // 最大边界子序列和等于两部分边界之和
         // 返回三个部分的最大子序列和
        return max3(leftMaxSubsequenceSum, maxBorderSum, rightMaxSubsquenceSum);        
    }

    public static void main(String[] args)
    {
        MaxSum maxSum = new MaxSum();
        int[] a = new int[]{4, -3, 5, -2, -1, 2, 6, -2};
        System.out.println(maxSum.MaxSubsequenceSum(a, 0, a.length - 1));
    }