C. C. Blog

Security Research, Algorithm and Data Structure

51 Nod1050 循环数组最大子段和

Problem

N个整数组成的循环序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的连续的子段和的最大值(循环序列是指n个数围成一个圈,因此需要考虑a[n-1],a[n],a[1],a[2]这样的序列)。当所给的整数均为负数时和为0。 例如:-2,11,-4,13,-5,-2,和最大的子段为:11,-4,13。和为20。

Solution

最大字段和最大,或者去掉中间某个最小字段和剩下的最大。

Code

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
#include<stdio.h>
#include<set>
#include<iostream>
#include<algorithm>
typedef long long ll;
typedef long double ld;
typedef double db;
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int n;
ll a[50020];
ll fmn[50020],fmx[50020],mn=0,mx=0,sum;
int main() {
io_opt;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
sum+=a[i];
fmx[i]=max(a[i],fmx[i-1]+a[i]);
mx=max(mx,fmx[i]);
fmn[i]=min(a[i],fmn[i-1]+a[i]);
mn=min(mn,fmn[i]);
}
cout<<max(mx,sum-mn);
return 0;
}
  • 本文作者: CCWUCMCTS
  • 本文链接: https://ccwucmcts.github.io/posts/64211/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!