1 /*最大子序和问题，从左到右和从右到左用了不同的方法
2 求从右到左时我用了
3 for(int i=0;i<n;++i)
4 {
5 if(b+p[i]>0)
6 {
7 b=b+p[i];
8 }
9 else
10 {
11 b=0;
12 }
13 if(b>max)max=b;
14 }
15 cout<<max<<endl;
16 这个方法。而从右到左求时，用这方法时
17 如下
18 sum2[n-1]=0;
19 for(int i=n-1;i>=1;--i)
20 {
21 if(sum2[i+1]+p[i]>0)
22 {
23 sum2[i]=sum2[i+1]+p[i];
24 }
25 else
26 {
27 sum2[i]=0;
28 }
29 if(sum2[i]>max)max=sum2[i];
30 一直W。。TAT.不知为何.所以换了个方法如下。
31 主要思路：两个不相交字串，一个从左到右求出sum1[i]为右边前i个数中最大字串（未必从第一个开始，也未必最后一个结束，的任意子串），
32 而从这时的i到n中求出最大子串值和其相加时，未必为最大和。所以先保证从右到左为最大，求出i，再从i到1求出。
33 再从和中挑出最大的，若两个都挑出最大的，用函数的话会超时很惨的。*/
34
35 #include<iostream>
36 #include<stdio.h>
37 using namespace std;
38 //=====================================================
39 #define M 50001
40 int k;
41 int p[M],sum1[M],sum2[M];
42 //=====================================================
43 int main()
44 {
45 int n;
46 int max=-M;
47 // freopen( "in.txt", "r", stdin);
48 //freopen( "out.txt", "w+", stdout);
49 scanf("%d",&k);
50 while(k--)
51 {
52 int n;
53 scanf("%d",&n);
54
55 int max=-M;
56 int m=-M;
57 scanf("%d",&p[0]);
58
59 sum1[0]=p[0];
60
61
62 for(int i=1;i<n;++i)
63 {
64 scanf("%d",&p[i]);
65 if(sum1[i-1]+p[i]>0)
66 {
67 sum1[i]=sum1[i-1]+p[i];
68 }
69 else
70 {
71 sum1[i]=0;
72 }
73 }
74 sum2[n-1]=p[n-1];
75 for(int i=n-1;i>=1;--i)
76 {
77 if(sum2[i]>0)
78 {
79 sum2[i-1]=sum2[i]+p[i-1];
80 }
81 else
82 {
83 sum2[i-1]=p[i-1];
84 }
85 if(sum2[i]>max)max=sum2[i];
86
87 if(sum1[i-1]+max>m)
88 {
89 m=sum1[i-1]+max;
90 }
91 }
92 printf("%d\n",m);
93 }
94 }
95
96
97
98
99
100
101
102
103
104