首页 > 代码库 > 51nod 1050 循环数组最大子段和
51nod 1050 循环数组最大子段和
题目链接:51nod 1050 循环数组最大子段和
1 #include<stdio.h> 2 #include<algorithm> 3 using namespace std; 4 const int N = 50001; 5 long long a[N]; 6 int main(){ 7 int n, i; 8 long long ma_ed, ans, sum = 0; 9 scanf("%d", &n);10 for(i = 1; i <= n; ++i){11 scanf("%I64d", &a[i]);12 sum += a[i];13 }14 ma_ed = a[1];15 ans = max(0LL, a[1]);16 for(i = 2; i <= n; ++i){//1~n求最大子段和17 if(ma_ed > 0)18 ma_ed += a[i];19 else20 ma_ed = a[i];21 ans = max(ma_ed, ans);22 }23 long long mi_ed = a[1], s = a[1];24 //最大字段和首尾相接情况25 for(i = 2; i <= n; ++i){26 if(mi_ed < 0)27 mi_ed += a[i];28 else29 mi_ed = a[i];30 s = min(mi_ed, s);31 }32 //首尾相接时,答案为序列数的总和 与 其中数相加最小的和(负值) 之差33 printf("%I64d\n", max(ans, sum - s));34 return 0;35 }
51nod 1050 循环数组最大子段和
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。