分而治之算法

主要的设计思想是：将一个难以解决的大问题，分割成几个规模较小的相似问题，逐个击破。其实这个算法并不陌生，在数据结构中很常见例如：折半查找，合并排序，快速排序，二叉树遍历（先左后右），二叉树排序树的查找算法。

算法思路：

可以用一个递归过程表示，分治法就是一种大规模问题与小规模问题关系的方法，是递归设计方法的一种具体策略，分治法在每一层递归上一般分为三个步骤：

1、分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题

2、解决：若子问题规模较小而容易被解决，则直接解决，否则再继续分解成更小规模的问题，直到容易解决

3、合并：将已求解的各个子问题的解，逐步合并成原问题的解

常见分为等分分治法和非等分治法

二分法

不同于现实中对问题的分解，需要考虑问题的重点，难点，承担人员的能力等来进行问题的分解和分配，在算法设计中每次一个问题分解成的子问题个数的一般是固定的，每个子问题的规模也是平均分配的。当每次都将问题分解成原问题的一半时，称为 二分法。 （二分法是分治法较为常用分解策略，折半查找，归并排序等算法都是采用此策略实现的）

Case1：金块问题

老板有一袋金块（共n块）。最优秀的雇员得到其中的最重的一块，最差的雇员得到最轻的一块，假设有一台比较重量的仪器，请使用最少的比较次数找出最重的金块

算法分析：

比较简单的方法是逐个进行查找，先拿两块比较重量，留下重的一个与下一块比较，直到全部比较完毕，就找到了最重的金子。（类似于选择排序）

算法设计：

maxmin(float a[],int n){
  max ==min =a[1];
    for(i=2;i<=n;i++){
        if(max<a[i]){
        max=a[i];
        }else if(min>a[i]){
            min=a[i];
        }
    }
}

算法中需要n-1次比较从而得到max，

最好的情况是金块是由小到大取出的，不需要进行与min的比较，共进行n-1次比较，

最坏的情况是金块由大到小取出的，需要再经过n-1次比较得到min，共进行2n-2次比较的

至于在平均的情况下，a（i）将有一般的时间比max大，因此平均比较数是 3（n-1）/2

Case2:求数列的最大子段和（不独立子问题）

给定n个元素的整数列（可能为负整数）a1，a2....an求形如：ai,ai+1,....aj(i,j=1.....n,i<=j)的子段，使其和为最大。当所有整数均为负整数时定义其最大子段和为0。例如当（a1,a2,a3,a4,a5,a6）=(-2,11,-4,13,-5,-2)时，最大子段和为i=2，j=4（下标从1开始）

问题分析：

若用二分法将实例中的数据分解成两组（-2，11，-4）和（13，-5，-2），第一个子问题的解是11，第二个子问题的解是13，两个子问题的解不能简单地得到问题的解。由此看出这个问题不能用二分法分解成为独立的两个子问题，子问题中间还有公共的子问题，这类问题称为子问题重叠类的问题。那么，怎样解决这类问题呢？（不独立子问题）

算法分析：

分解方法还是用二分法，虽然分解后的子问题并不独立，但通过对重叠的子问题进行专门处理，并对所有的问题合并进行设计，就可以用二分法策略解决问题。

如果将所给的序列a【1：n】分为长度相等的两段a【1 :（n/2）】和a【（n/2）+1:n】分别求出这两段的最大子段和，则a【1：n】的最大子段和有三种情形：

1. a【1：n】的最大子段和与a[1:(n/2)]的最大子段和相同
2. a【1：n】的最大子段和与a[(n/2)+1：n]的最大子段和相同
3. a【1：n】的最大子段和与a[i:j],且1≤i≤(n/2), (n/2)+1≤j≤n;

对于情况1，2可分别递归求得。但是对于情况3，a[(n/2)] 和a[(n/2)+1]一定在最优的子序列中，因此可得a[i:(n/2)]的最大值s1，并计算出a[(n/2)+1:j]中的最大值s2，则情况3的最优值为 s1+s2

算法设计：

int max_sum3 (int a[],int n)
{
return (max_sub_sum (a,1,n));
}
max_sub_sum(int a [],int left,int right){
int center,i,j,sum,left_sum,right_sum,s1,s2,lefts,rights;
    if(left =right){
      if(a[left]>0){
            return(a[left]);
      }else{
        return (0);
        }
    }else{
    center =(left +right )/2;
        left_sum=max_sub_sum(a,left,center);
        right_sum=max_sub_sum(a,center+1,right);
        s1=0;
        lefts=0;
        for(i=center;i>=left;i--){
            { lefts=lefts+a[i];
              if(lefts>s1){
                s1=lefts;
                }
            }
        s2=0;righs=0;
        for(i=center+1;i<=right;i++){
            rights=rights+a[i];
              if(rights>s2){
                    s2=rights;
                }
        }
        }
        if(s1+s2<left_sum and right_sum <left_sum){
            return(left_sum);
        }      
        if(s1+s2<right ){
            return(right_sum);
        }
        return (s1+s2);
    }
}