解决最大连续子序列和的两种方法：分治，动态规划。
分治时间复杂度虽然更高，但我还是写了一遍加深对这种思想的理解：将一个问题分治成若干个小的同样思路的子问题来解决。本题将所求序列等分成左右两个子序列，愿序列的最大子序列和必是左序列最大子序列和，有序列最大子序列和，，跨左右子序列最大和三者中的最大者。
动态规划：用dp［i］更新dp［i＋1］就行。
分治：
//// main.cpp// 1109//// Created by Fangpin on 15/3/9.// Copyright (c) 2015年 FangPin. All rights reserved.//#include <iostream>#include <cstdio>#include <cstring>using namespace std;int a[104];int f(int l,int r){int m=(l+r)>>1;if(l>=r) return a[l];int left=f(l,m);int right=f(m+1,r);int mid=-1e10,sum=0;for(int i=m;i>=0;–i){sum+=a[i];mid=max(mid,sum);}sum=0;int maxn=-1e10;for(int i=m+1;i<=r;++i){sum+=a[i];maxn=max(maxn,sum);}mid+=maxn;if(left>=mid && left>=right) return left;else if(right>=left && right>=mid) return right;else return mid;}int main(int argc, const char * argv[]) {// insert code here…int t;scanf("%d",&t);while(t–){int n;scanf("%d",&n);for(int i=0;i<n;++i)scanf("%d",&a[i]);printf("%d\n",f(0,n-1));}return 0;}动态规划：
//// main.cpp// 1109//// Created by Fangpin on 15/3/9.// Copyright (c) 2015年 FangPin. All rights reserved.//#include <iostream>#include <cstdio>#include <cstring>using namespace std;int a[104],dp[104];int main(int argc, const char * argv[]) {// insert code here…int t;scanf("%d",&t);while(t–){int n;scanf("%d",&n);for(int i=0;i<n;++i)scanf("%d",&a[i]);memset(dp,0,sizeof(dp));dp[0]=a[0];int ans=a[0];for(int i=1;i<n;++i){if(dp[i-1]>0)dp[i]=dp[i-1]+a[i];else dp[i]=a[i];ans=max(ans,dp[i]);}printf("%d\n",ans);}return 0;}
天才就是这样，终身努力，便是天才。
