看书、思考、写代码。

/***************************************

 * copyright@hustyangju

 * blog: http://blog.csdn.net/hustyangju

 * 题目：分治法求数组最大连续子序列和

 * 思路：分解成子问题+合并答案

 * 时间复杂度：O(n lgn)

 * 空间复杂度：O（1）

***************************************/

#include <iostream>

using namespace std;

template<class type>

class max_subarray

{

public:

    max_subarray(type *p):_p(p){}

    ~max_subarray(){}

    type max_aside_subarray(int s,int e);

protected:

    type max_cross_subarray(int s,int m,int e);

    type _max(type a,type b,type c);

private:

    type *_p;

};

template<class type>

type max_subarray<type>::_max(type a, type b, type c)

{

    if((a>=b)&&(a>=c))

        return a;

    else if((b>=a)&&(b>=c))

        return b;

    else

        return c;

}

template<class type>

type max_subarray<type>::max_cross_subarray(int s, int m, int e)

{

    type left_sum=*(_p+m);

    type right_sum=*(_p+m+1);

    for(int i=m;i>=s;i--)

    {

        type sum=0;

        sum+=*(_p+i);

        if(sum>left_sum)

            left_sum=sum;

    }//for

    for(int i=m+1;i<=e;i++)

    {

        type sum=0;

        sum+=*(_p+i);

        if(sum>right_sum)

            right_sum=sum;

    }//for

    return(left_sum+right_sum);

}

template<class type>

type max_subarray<type>::max_aside_subarray(int s, int e)

{

    int m=0;

    type left_sum,right_sum,cross_sum;

    if(s==e)

        return(*(_p+s));

    else

        m=int((s+e)/2);

    left_sum=max_aside_subarray(s,m);

    cross_sum=max_cross_subarray(s,m,e);

    right_sum=max_aside_subarray(m+1,e);

    return _max(left_sum,cross_sum,right_sum);

}

int main()

{

            int array1[10]={1,-2,-3,4,5,6,-7,-8,9,10};

           // float array2[10]={1.0,-2.0,-3.0,4.0,5.2,6.0,-7.0,-8.0,9.0,-10.0};

            max_subarray<int> mysubarray1(array1);

            //max_subarray<float>mysubarray2(array2);

            cout<<"max sum of sub array is: ";

            cout<<mysubarray1.max_aside_subarray(0,9)<<endl;

           // cout<<"max sum of sub array is: ";

            //cout<<mysubarray2.max_aside_subarray(0,9)<<endl;

}