http://poj.org/problem?id=2750
题意：在一个圈中取若干个相邻的数，求他们的最大序列和。不能够同时取所有的数。
看了一篇解题报告写的很详细。。http://blog.csdn.net/non_cease/article/details/7437690
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <algorithm> 4 #include <string.h> 5 const int N=100010; 6 using namespace std; 7 struct node 8 { 9 int l,r,sum,minsum,maxsum; 10 int lmax,rmax,lmin,rmin; 11 } Tree[4*N]; 12 int a[N]; 13 void pushup(int rt) 14 { 15 int l = 2*rt; 16 int r = 2*rt+1; 17 Tree[rt].sum=Tree[l].sum+Tree[r].sum; 18 Tree[rt].minsum=min(min(Tree[l].minsum,Tree[r].minsum),Tree[l].rmin+Tree[r].lmin); 19 Tree[rt].maxsum=max(max(Tree[l].maxsum,Tree[r].maxsum),Tree[l].rmax+Tree[r].lmax); 20 Tree[rt].lmax=max(Tree[l].lmax,Tree[l].sum+Tree[r].lmax); 21 Tree[rt].rmax=max(Tree[r].rmax,Tree[r].sum+Tree[l].rmax); 22 Tree[rt].lmin=min(Tree[l].lmin,Tree[l].sum+Tree[r].lmin); 23 Tree[rt].rmin=min(Tree[r].rmin,Tree[r].sum+Tree[l].rmin); 24 } 25 void build(int l,int r,int rt) 26 { 27 Tree[rt].l = l; 28 Tree[rt].r = r; 29 if (l==r) 30 { 31 Tree[rt].sum=Tree[rt].minsum=Tree[rt].maxsum=a[r]; 32 Tree[rt].lmax=Tree[rt].rmax=Tree[rt].lmin=Tree[rt].rmin=a[r]; 33 return ; 34 } 35 int mid = (l+r)>>1; 36 build(l,mid,2*rt); 37 build(mid+1,r,2*rt+1); 38 pushup(rt); 39 } 40 void update(int pos,int val,int rt) 41 { 42 if (Tree[rt].l==Tree[rt].r) 43 { 44 Tree[rt].sum=Tree[rt].minsum=Tree[rt].maxsum=val; 45 Tree[rt].lmax=Tree[rt].rmax=Tree[rt].lmin=Tree[rt].rmin=val; 46 return ; 47 } 48 int mid=(Tree[rt].l+Tree[rt].r)>>1; 49 if (pos<=mid) 50 update(pos,val,2*rt); 51 else 52 update(pos,val,2*rt+1); 53 pushup(rt); 54 } 55 int main() 56 { 57 int n,m,pos,val; 58 scanf("%d",&n); 59 for (int i = 1; i <=n; i++) 60 { 61 scanf("%d",&a[i]); 62 } 63 build(1,n,1); 64 scanf("%d",&m); 65 while(m--) 66 { 67 scanf("%d%d",&pos,&val); 68 update(pos,val,1); 69 if(Tree[1].sum==Tree[1].maxsum) 70 { 71 printf("%d ",Tree[1].sum-Tree[1].minsum); 72 } 73 else 74 { 75 printf("%d ",max(Tree[1].maxsum,Tree[1].sum-Tree[1].minsum)); 76 } 77 } 78 return 0; 79 }