P1115 最大子段和 题解

P1115 最大子段和 - 洛谷

题目大意：

从一个序列中找出和最大的一段连续区间并输出和。

解法一 前缀和：

因题中求的是区间和，所以应想到前缀和。

而一个区间和可以通过前缀和数组首尾的差来求（a[r]-a[l]）

而要使差最大，应尽量使被减数大，减数小。

也就是a[r]大，a[l]小，尾大头小。

则只需找出尽量大的尾和尽量小的头即可。

我们可以先算出每个头对应的尾存入数组，再枚举头，比较目前的区间和即可。

时间复杂度为O(2n)。

#include<bits/stdc++.h> using namespace std; int a[200005],b[200005]={},c[200005]; int main(){ int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; b[i]=b[i-1]+a[i];//前缀和数组 } c[n+1]=-1e9;//注意：题中包含负数 for(int i=n;i>=1;i--){//注意：从后往前 c[i]=max(c[i+1],b[i]);//求c[i]~c[n]中的最大值 } int maxx=-1e9;//注意：和有可能是负数 for(int i=0;i<=n;i++){ maxx=max(maxx,c[i+1]-b[i]);//求最大和 } cout<<maxx; return 0; }