1.實踐題目名稱

最大子列和問題

2.問題描述

6
-2 11 -4 13 -5 -2

20

3.算法描述

              本題需要利用分治法分解主問題，對于本問題，在暴力窮舉的算法的思想上進(jìn)行優(yōu)化，把所求區(qū)間從中間一分為二，將問題劃分為求左區(qū)間、右區(qū)間、橫跨左右區(qū)間的最大子列和的問題。左右區(qū)間的求解利用基礎(chǔ)的遞歸方式完成，中間的最大子列和另外做特殊處理，最后將所求的三者進(jìn)行對比得到答案，這種方式能優(yōu)化時間復(fù)雜度到nlog(n)，大大提高效率。

代碼：

#include<bits/stdc++.h>
using namespace std;
int three_max(int a,int b,int c){
if(a>b&&a>c) return a;
if(b>a&&b>c) return b;
if(c>a&&c>b) return c;
}
int max_subsequence(int sum[],int left,int right){
int max_left=0,max_right=0;
int max_border_left=0,max_border_right=0;
int sum_left=0,sum_right=0;
if(left==right) return 0>sum[left]?0:sum[left];
int mid=(left+right)/2;
max_left=max_subsequence(sum,left,mid);
max_right=max_subsequence(sum,mid+1,right);
for(int i=mid;i>=left;--i){
sum_left+=sum[i];
if(sum_left>max_border_left) max_border_left=sum_left;
}
for(int i=mid+1;i<=right;++i){
sum_right+=sum[i];
if(sum_right>max_border_right) max_border_right=sum_right;
}
return three_max(max_border_left+max_border_right,max_left,max_right);
}
int main(){
int k;
cin>>k;
int sum[k];
for(int i=0;i<k;++i){
cin>>sum[i];
}
cout<<max_subsequence(sum,0,k-1);
return 0;
}

4.算法時間復(fù)雜度分析　

              設(shè)算法的復(fù)雜度為T(N)，

　　　　第一步分解為兩個子問題為O(1)

　　　　第二步分別求解兩個子問題為O(N/2)*2

　　　　第三步合并子問題為O(N)

　　　　等式為：T(N)=O(1)+2T(N/2)+O(N)

　　　　得：T(N)=O（nlogn）

5.心得體會（對本次實踐收獲及疑惑進(jìn)行總結(jié)）

　　　　本次的題目就我看來算是一道分治法的經(jīng)典例題，雖然一開始我并不能理解為什么一定要分而治之，因為在我看來都是要遍歷一遍所有數(shù)據(jù)，但是后來我逐漸想通了這種方法能節(jié)省的時間，也深刻的認(rèn)識到好算法的重要性。