P1115 最大子段和 题解

P1115 最大子段和 - 洛谷题目大意从一个序列中找出和最大的一段连续区间并输出和。解法一 前缀和因题中求的是区间和所以应想到前缀和。而一个区间和可以通过前缀和数组首尾的差来求a[r]-a[l]而要使差最大应尽量使被减数大减数小。也就是a[r]大a[l]小尾大头小。则只需找出尽量大的尾和尽量小的头即可。我们可以先算出每个头对应的尾存入数组再枚举头比较目前的区间和即可。时间复杂度为O(2n)。#includebits/stdc.h using namespace std; int a[200005],b[200005]{},c[200005]; int main(){ int n; cinn; for(int i1;in;i){ cina[i]; b[i]b[i-1]a[i];//前缀和数组 } c[n1]-1e9;//注意题中包含负数 for(int in;i1;i--){//注意从后往前 c[i]max(c[i1],b[i]);//求c[i]~c[n]中的最大值 } int maxx-1e9;//注意和有可能是负数 for(int i0;in;i){ maxxmax(maxx,c[i1]-b[i]);//求最大和 } coutmaxx; return 0; }