看書、思考、寫代碼。

/**************************************** copyright@hustyangju * blog: http://blog.csdn.net/hustyangju * 題目：分治法求數(shù)組最大連續(xù)子序列和* 思路：分解成子問題+合并答案* 時間復雜度：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;elsereturn 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;}//forfor(int i=m+1;i<=e;i++){type sum=0;sum+=*(_p+i);if(sum>right_sum)right_sum=sum;}//forreturn(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));elsem=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; }

《新程序員》：云原生和全面數(shù)字化實踐50位技術專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的《github一天一道算法题》：分治法求数组最大连续子序列和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。