前缀和算是一种预处理,能降低时间复杂度从而达到一定的优化
那么话不多说,我们先从一个简单的例子入手。
T组数据,每组有N个数,然后给出R,L。目标是让你求出在区间[R,L]之间的和。(0<= R < L <=N)。
那么我们怎么用前缀和来处理呢?
定义一个数组sum[], sum[0] = 0;用sum[i]表示(a[1]+a[2]+……+a[i]),这样的话我们就很容易得到结果了!
#include<bits/stdc++.h>
#define maxn 1002
using namespace std;
int a[maxn];
//int sum[maxn];
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int res;
cin>>res;
a[0] = res;//熟练的话我们其实只用一个数组就行了
for(int i=1;i<n;i++){
cin>>a[i];
a[i] = a[i-1]+a[i];
}
int r,l;
cin>>r>>l;
cout<<a[l-1]-a[r-1]<<endl;
}
return 0;
}
最大数问题 题意:N个小朋友围成一圈,然后从中选取若干个连续的数,加起来,得到最大的和。
有了前面的铺垫,相比这个就很简单了吧,但难度在于小朋友是围成一圈的,上一题相当于小朋友是站成一队!啊哈哈哈。
思路:先统计前缀和,结果有两种,一是不跨越首尾,直接找到前缀和差值最大即可;二是跨越首尾,找到前缀和差值最小再用全部数字的和减掉该值,两种情况取大值就行,遍历数组可同时维护这两个值。
直接代码
# include <iostream>
# include <cstring>
# include <cstdio>
# include <algorithm>
# define INF 0x3f3f3f3f
using namespace std;
int a[100001], b[100001];
int main()
{
int n, imax = -INF, imin = INF, ans;
freopen("maxsum.in", "r", stdin);
freopen("maxsum.out", "w", stdout);
scanf("%d",&n);
memset(b, 0, sizeof(b));
for(int i=1; i<=n; ++i)
{
scanf("%d",&a[i]);
b[i] = b[i-1] + a[i];
}
ans = a[n];
for(int i=n; i>=1; --i)
{
imax = max(imax, b[i]);
imin = min(imin, b[i]);
ans = max(ans, max(imax-b[i], b[n]-imin+b[i]));
}
printf("%d\n",ans);
return 0;
}