大家好，又见面了，我是全栈君。
看书、思考、写代码。
/***************************************
* 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;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/115874.html原文链接：https://javaforall.net
