首页 > 其他 > 详细

1049 最大子段和

时间:2018-04-26 20:53:32      阅读:176      评论:0      收藏:0      [点我收藏+]
基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题
技术分享图片 收藏
技术分享图片 关注
N个整数组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的连续子段和的最大值。当所给的整数均为负数时和为0。
 
例如:-2,11,-4,13,-5,-2,和最大的子段为:11,-4,13。和为20。
Input
第1行:整数序列的长度N(2 <= N <= 50000)
第2 - N + 1行:N个整数(-10^9 <= A[i] <= 10^9)
Output
输出最大子段和。
Input示例
6
-2
11
-4
13
-5
-2
Output示例
20

dp过去,找到最大的。
 1 #include<iostream>
 2 using namespace std;
 3 int a[500050];
 4 int main(){
 5     int n;
 6     cin>>n;
 7     for(int i=0;i<n;i++) 
 8         cin>>a[i];
 9     long long sum=0,maxn=0,ss=0;
10     for(int i=0;i<n;i++){
11         sum+=a[i];
12         sum=max(sum,ss);
13         maxn=max(maxn,sum);
14     }
15     cout<<maxn<<endl;
16     return 0;
17 }

 

1049 最大子段和

原文:https://www.cnblogs.com/zllwxm123/p/8954591.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!