解题思路：环形数组最大字串，穿过和不穿过的DP
解题代码：
1 // File Name: c.cpp 2 // Author: darkdream 3 // Created Time: 2015年04月12日 星期日 19时52分24秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 26 using namespace std; 27 int t; 28 int n; 29 int sum[100005]; 30 int mxsum[100005]; 31 int a[100005]; 32 int main(){ 33 scanf("%d",&t); 34 while(t--) 35 { 36 int n ; 37 memset(sum,0,sizeof(sum)); 38 scanf("%d",&n); 39 int tsum = 0 ; 40 int ans = 0 ; 41 int asum = 0 ; 42 for(int i = 1;i <= n;i ++) 43 { 44 scanf("%d",&a[i]) ; 45 if(tsum <= 0 ) 46 { 47 tsum = 0 ; 48 } 49 asum += a[i]; 50 tsum += a[i]; 51 mxsum[i] = max(mxsum[i-1],asum); 52 ans = max(ans,tsum); 53 } 54 tsum = 0 ; 55 for(int i = n; i >= 1;i--){ 56 tsum +=a[i]; 57 ans = max(tsum+mxsum[i-1],ans) ; 58 } 59 printf("%d ",ans); 60 } 61 return 0; 62 }