题目大意：给出一段数组，然后让你求出最大的子串和，并记录这个最大的子串和的开始位置和结束的位置。
解题报告：动态规划题，用最大子串和。即假设现在要求的是数组a[]的最大子串和，先定义一个f[]数组，首先将f[]数组初始化，判断a[1]是否大于0，若大于等于0，
则f[1]=a[1],若a[1]<=0，则f[1]=0,接下来用递归了，递归方程为f[i]=(f[i-1]+a[i])>0? f[i-1]+a[i]:0，递归完了之后再求出f[]数组里面的最大值，就是要求的最大子串和。然后就是求最大子串和的位置的问题，这个只要当判断到了a[i]小于0的时候就把当前的串的位置记录在另一个结构体里面，也可以直接把f[]数组和直接定义成结构体。
View Code
1 #include<iostream> 2 #include<stdio.h> 3 using namespace std; 4 int T,a[1000010]; 5 struct fun { 6 int date; 7 int front,rear; 8 }f[1000010]; 9 int ma(int x,int y) { 10 return (x>y? x:y); 11 } 12 int main() { 13 scanf("%d",&T); 14 for(int l=1;l<=T;++l) { 15 int n; 16 scanf("%d",&n); 17 for(int i=1;i<=n;++i) 18 scanf("%d",&a[i]); 19 int k=0; 20 for(int i=1;i<=n;++i) 21 if(a[i]>0) 22 k=1; 23 int max=1; 24 if(k){ 25 for(int i=0;i<n;++i) 26 f[i].front=1; 27 f[0].date=0; 28 int biaoji=1; 29 for(int i=1;i<=n;++i) { 30 if(f[i-1].date+a[i]<0 ) 31 biaoji=i+1; 32 else 33 f[i].front=biaoji; 34 f[i].rear=i; 35 f[i].date=ma(0,f[i-1].date+a[i]); 36 } 37 for(int i=2;i<=n;++i) 38 if(f[i].date>f[max].date) { 39 max=i; 40 f[max].rear=max; 41 } 42 } 43 else if(k==0) { 44 int min=1; 45 for(int i=2;i<=n;++i) 46 if(a[i]>a[min]) 47 min=i; 48 max=min; 49 f[max].date=a[min]; 50 f[max].front=min; 51 f[max].rear=min; 52 } 53 printf("Case %d:\n%d %d %d\n",l,f[max].date,f[max].front,f[max].rear); 54 if(l!=T) 55 printf("\n"); 56 } 57 return 0; 58 }