-
最大子段和
2020-01-23 19:48:31最大子段和题目描述
给出一段序列,选出其中连续且非空的一段使得这段和最大。
输入格式
第一行是一个正整数N,表示了序列的长度。
第二行包含N个绝对值不大于10000的整数Ai,描述了这段序列。
输出格式
一个整数,为最大的子段和是多少。子段的最小长度为1。
输入输出样例
输入 #1
7 2 -4 3 -1 2 -4 3
输出 #1
4
说明/提示
【样例说明】
2,-4,3,-1,2,-4,3中,最大的子段和为4,该子段为3,−1,2.
【数据规模与约定】
对于40%的数据,有N ≤ 2000
对于100%的数据,有N ≤ 200000
#include<bits/stdc++.h> using namespace std; int n[200001],p,ans[200001]={0};//数组定义在外面 int main() { int sum=-9999999;//最小值 cin>>p;//个数 for(int i=1;i<=p;i++) { cin>>n[i]; ans[i]=max(ans[i-1]+n[i],n[i]);//等于前一个最大的字段加上这个数和这个数的最大值,不是顺着前一个,就是自己起一个头,看看那个的 sum=max(sum,ans[i]);//记录最大的 } cout<<sum;//输出 return 0; }
收藏数
5,196
精华内容
2,078
-
仿Spy++ 将DLL代码注入EXE的三种方法.zip
-
Go 永久阻塞的方法
-
宾得Kx使用手册.pdf
-
PHP支付宝微信支付配置教程
-
转行做IT-第8章 类与对象、封装、构造方法
-
Laya 2.0 开发3D小游戏 入门教学
-
Spring5:@Autowired注解、@Resource注解和@Service注解
-
Unity游戏开发之数字华容道
-
转行做IT-第2章 HTML入门及高级应用
-
【2021】UI自动化测试Selenium3
-
Linux与数据库基础
-
PHP7.2源码安装
-
MindSpore张量mindspore::tensor
-
MindSpore技术理解(下)
-
30个生涯锦囊,带你跳出迷茫,找到适合你的职业方向
-
软件设计实践.doc
-
第1章 Java入门基础及环境搭建【java编程进阶】
-
UNLOCK.iso加密解密软件和狗的一些资料
-
基于solidworks中的stewart平台建模
-
转行做IT-第7章 数组