首页 > 代码库 > 51nod 1050 循环数组最大子段和
51nod 1050 循环数组最大子段和
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1050
题意：
思路：
情况无非分为两种：
①正常的最大子段和。
②首尾相连的最大子段和，此时中间的那段肯定是最小子段和，用总的sum-最小子段和即可。
最后比较两者大小。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<stack> 7 #include<queue> 8 #include<cmath> 9 #include<map>10 using namespace std;11 12 typedef long long LL;13 const int maxn=50000+5;14 15 int n;16 LL a[maxn];17 LL d[maxn];18 19 int main()20 {21 //freopen("D:\\input.txt","r",stdin);22 while(~scanf("%d",&n))23 {24 LL sum=0;25 for(int i=1;i<=n;i++)26 {27 scanf("%lld",&a[i]);28 sum+=a[i];29 }30 LL MAX=0,MIN=0x3f3f3f3f;31 d[0]=0;32 for(int i=1;i<=n;i++)33 {34 d[i]=max(a[i],d[i-1]+a[i]);35 MAX=max(MAX,d[i]);36 }37 d[0]=0;38 for(int i=0;i<=n;i++)39 {40 d[i]=min(a[i],d[i-1]+a[i]);41 MIN=min(MIN,d[i]);42 }43 printf("%lld\n",max(MAX,sum-MIN));44 }45 return 0;46 }
51nod 1050 循环数组最大子段和
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。