最大字段和

1049 最大子段和

基准时间限制:1 秒 空间限制:131072 KB

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
 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 const int MAXN = 50000+5;
 5 int a[MAXN];
 6 int main()
 7 {
 8     int n;
 9     while(~scanf("%d",&n))
10     {
11         for(int i=1; i<=n; i++)
12             scanf("%d",&a[i]);
13         long long Max = 0, sum = 0;
14         for(int i=1; i<=n; i++)
15         {
16             //cout << sum << endl;
17             if(sum >= 0)
18                 sum += a[i];
19             else
20                 sum = a[i];
21             if(sum > Max)
22                 Max = sum;
23         }
24         printf("%lld\n",Max);
25     }
26     return 0;
27 }
时间: 04-09

最大字段和的相关文章

SQL查询字段添加括号报错:Operand should contain 1 column(s)

SQL语句:查询连个字段的信息 SELECT (menu_id,menu_captions) FROM bsdb.menulist a WHERE a.menu_id like ('2_'); 然后,因为这是在存储过程中的一个语句所以,在执行存储过程的时候编译不会报错,但是执行的时候却汇报错:Operand should contain 1 column(s):原因不好解释: 下面是官方发解释(MYSQL):https://dev.mysql.com/doc/refman/5.0/en/row-

SqlServer给一个表增加多个字段语法

添加字段语法 alter table table_name add column_name +字段类型+ 约束条件 给一个表增加多个字段: use NatureData go alter table XunHu add MaleCount varchar(50) null, FemaleCount varchar(50) null, SubadultCount varchar(50) null, LarvaeCount varchar(50) null, TraceType varchar(50

查询字段描述sql-postgresql

查询字段描述sql SELECT 'comment on column ' || n.nspname ||'.'|| c.relname || '.' || a.attname ||' is '''|| col_description(a.attrelid,a.attnum) ||''';' FROM pg_class as c join pg_attribute as a on a.attrelid = c.oid join pg_namespace n on c.relnamespace=n

passwd、shadow、group结构及各字段含义

/etc/password结构 sample:root:x:0:0:root:/root:/bin/bash 账号名称 密码 UID GID 用户信息说明 家目录 Shell root x 0 0 root /root /bin/bash /etc/shadow结构: sample:root:$1$/30QpE5e$y9N/D0bh6rAACBEz.hqo00:14126:0:99999:7::: 账号名称 密码 最近更动密码的日期 密码不可被更动的天(0代表随时可以变动) 密码需要重新变更的天

快学Scala 第二十一课 (初始化trait的抽象字段)

初始化trait的抽象字段: trait Logged { println("Logged constructor") def log(msg: String){ println("Logged")} } trait FileLogger extends Logged { var filename: String override def log(msg: String) { println("filename:" + filename) } }

Sql Server将一列字段拼接成字符串方法

最近在项目中遇到个问题,需要将表中某列字段合并成字符串输出,如果直接通过代码全部读取出来,再遍历进行拼接显然不是最好的方法,所以想着能否在数据读取的时候直接拼接好返回,网上搜了可通过for xml来实现. 首先,准备好需要的数据,脚本如下: if exists (select * from sysObjects where id=object_id('Student')) drop table Student go create table Student ( Id int, Name varc

MySQL指定模糊查询范围 或 获取或者查询数据库字段的特定几位

SUBSTR 函数 正常的: select * from sky_user WHERE name LIKE "%name%" 现在我需要匹配name的前五位 select * from sky_user WHERE SUBSTR(name,1,5) LIKE "%name%" SQL 中的 substring 函数是用来抓出一个栏位资料中的其中一部分.这个函数的名称在不同的资料库中不完全一样: MySQL: SUBSTR( ), SUBSTRING( ) Oracl

Oracle 增加修改删除字段

添加字段的语法:alter table tablename add (column datatype [default value][null/not null],-.); 修改字段的语法:alter table tablename modify (column datatype [default value][null/not null],-.); 删除字段的语法:alter table tablename drop (column); 添加.修改.删除多列的话,用逗号隔开. 使用alter

[Elasticsearch] 关于字段重复值的常用查询和操作总结

1. 取得某个索引中某个字段中的所有出现过的值 这种操作类似于使用SQL的SELECT UNIQUE语句.当需要获取某个字段上的所有可用值时,可以使用terms聚合查询完成: GET /index_streets/_search?search_type=count { "aggs": { "street_values": { "terms": { "field": "name.raw", "siz

MySQL字段属性介绍

这次Qi号分享MySQL字段属性简介.下面资料是Qi号搜集大量资料与个人理解的整理.看到最后有福利哦基友们 前言 MySQL提供了一组可以赋给表中各个列的数据类型,每个类型都强制数据满足为该数据类型预先确定的一组规则,例如大小.类型及格式. 这里先总结数据类型.MySQL中的数据类型大的方面来分,可以分为:日期和时间.数值,以及字符串.下面就分开来进行总结. 日期和时间数据类型 MySQL数据类型   含义 date 3字节,日期,格式:2014-09-18 time 3字节,时间,格式:08: