最大连续和

题目描述：
给出一个长度为n 的序列A1,A2,...,An，求最大连续和。换句话说，要求找到1<=i<=j<=n，使得Ai+Ai+1+...+Aj 尽量大。

输入格式：
第一行输入n(1<=n<=50000)。
接下来1 行输入序列的n 个元素，第i+1 行为Ai(|Ai|<=10000)。

输出格式：
输出一个数表示最大连续和。

样例输入：

4
2 -1 3 -2

样例输出：
4

数据范围：
30%的数据n<=100;
60%的数据n<=10000;
100%的数据n<=50000。

连续和就是区间和嘛，首先用前缀和处理一下，则sum[L, R] = sum[R] - sum[L - 1]。

那么我们只要枚举sum[R], 让sum[L - 1]尽量小，并尝试更新ans即可。

写法就是开一个Min[i]记录前缀1到i的最小值，然后ans = max(ans, sum[R] - Min[R]).

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<cstring>
 6 using namespace std;
 7 #define rep(i, a, n) for(int i = a; i <= n; ++i)
 8 #define per(i, n, a) for(int i = n; i >= a; --i)
 9 typedef long long ll;
10 const int maxn = 5e4 + 5;
11 const int INF = 0x3f3f3f3f;
12 int n, a[maxn];
13 ll sum[maxn], Min[maxn], minn = 0;
14 ll ans = -INF;
15 int main()
16 {
17   scanf("%d", &n);
18   rep(i, 1, n) scanf("%d", &a[i]);
19   rep(i, 1, n) sum[i] = sum[i- 1] + a[i];
20   rep(i, 0, n)
21     {
22       minn = min(sum[i] , minn);
23       Min[i] = minn;
24     }
25   rep(i, 1, n)
26       ans = max(ans, sum[i] - Min[i]);
27   printf("%lld
",ans);
28   return 0;
29 }

再想一想，会发现其实前缀和和前缀最小值都没必要存，因为并没有用到历史前缀数组，枚举R的时候现更新就行。

改进代码

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<cstring>
 6 using namespace std;
 7 #define rep(i, a, n) for(int i = a; i <= n; ++i)
 8 #define per(i, n, a) for(int i = n; i >= a; --i)
 9 typedef long long ll;
10 const int maxn = 5e4 + 5;
11 const int INF = 0x3f3f3f3f;
12 int n;
13 ll a[maxn], sum = 0, Min = INF; 
14 ll ans = -INF;
15 int main()
16 {
17   scanf("%d", &n);
18   rep(i, 1, n) scanf("%lld", &a[i]);
19   rep(i, 0, n)
20     {
21         sum += a[i];        //相当于sum[R]
22         Min = min(Min, sum);    //相当于Min[R]
23         ans = max(ans, sum - Min);
24     }
25   printf("%lld
",ans);
26   return 0;
27 }