题目链接：
https://www.luogu.com.cn/problem/U549625
思路：
要求区间和，可以想到用前缀和数组，区间和即为 pre[r]-pre[l-1]，要求最大化区间和即最大化 pre[r]-pre[l-1]，对于固定的 i，，所以我们其实是在 。
这里可以开三个循环去做一下，两个子循环分别是枚举左端点和右端点。会超时。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define PII pair<int,int>
const int N=2e5+5;
int a[N];
int s[N];
void solve()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
s[i]=s[i-1]+a[i];
}
for(int i=1;i<=n;i++)
{
int ma=-1e18;
for(int l=1;l<=i;l++)
{
for(int r=i;r<=n;r++)
{
int sum=s[r]-s[l-1];
ma=max(ma,sum);
}
}
cout<<ma<<" ";
}
}
signed main(){
IOS
int t=1;
while(t--)
{
solve();
}
}
|
所以我们需要在 i 的左边找到一个最小的 pre[k] 在 i 的右边找到一个最大的 pre[r]。这样可以优化掉循环。
正解代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define PII pair<int,int>
const int N=2e5+5;
int a[N];
int s[N];
int c[N];
void solve()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
s[i]=s[i-1]+a[i];
}
c[n+1]=-1e18;
for(int i=n;i>0;i--)
{
c[i]=max(c[i+1],s[i]);
}
int mi=0;
for(int i=1;i<=n;i++)
{
int cur=c[i]-mi;
cout<<cur<<" ";
mi=min(mi,s[i]);
}
}
signed main(){
IOS
int t=1;
while(t--)
{
solve();
}
}
|
