最大子段和

题目描述:

N个整数组成的序列a11,a22,a33,…,ann, 求该序列如aii+ai+1i+1+…+ajj的连续子段和的最大值。当所给的整数均为负数时和为0。
例如:-2,11,-4,13,-5,-2,和最大的子段为:11,-4,13。和为20。
Input
第1行:整数序列的长度N(2 <= N <= 50000)
第2 - N + 1行:N个整数(-10^9 <= Aii <= 10^9)
Output
输出最大子段和。
Sample Input
6
-2
11
-4
13
-5
-2
Sample Output
20

AC代码:

#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string.h>
#include <math.h>
#define min(a,b) a<b?a:b;
using namespace std;
long long a[50000+5];
long long ans;
int main()
{
	int n,i;
	cin>>n;
	for(i=0;i<n;i++)
	{
		cin>>a[i];
		ans=max(ans,a[i]);
	}
	if(ans>=0)
	{
		long long sum=0;
		for(i=0;i<n;i++)
		{
			if(sum+a[i]<0)
				sum=0;
			else
				sum+=a[i];
			ans=max(ans,sum);
		}
	}
	cout<<ans<<endl;
	return 0;
}

热门文章

暂无图片
编程学习 ·

传说中的中国复杂报表都长什么样?有什么特点?

最开始中国式报表这个术语是针对国外的报表工具来说的,当时国外的报表工具只能做一些格式很规整的报表,到了中国以后发现有很多报表做不出来,或者做起来极不方便,还需要大量的人工编程。这些报表成了国外报表工具的恶梦,于是把复杂难做的报表称为“中国式”的。这些很难做…
暂无图片
编程学习 ·

用类来模拟(栈)操作

用类来模拟(栈)操作 #include <cstdio> #include <iostream> #include <cmath> #include <cstring>using namespace std;template<typename T>class Stack { public:Stack(int size =10){MAX_SIZE =10;tp =new T[size];this->size =0;}~Sta…
暂无图片
编程学习 ·

spring+mybatis日志

spring4默认日志是log4j, spring5默认日志是JUL spring4下使用JCL时,如果有log4j的jar,用的具体实现类是log4j,否则用的具体实现类是JUL spring4下使用JCL时,用的具体实现类是JUL1、spring4下日志加载顺序//循环for(int i=0; i<classesToDiscover.length && resu…
暂无图片
编程学习 ·

转 C++常用设计模式

适配器模式可以将一个类的接口转换成客户端希望的另一个接口,使得原来由于接口不兼容而不能在一起工作的那些类可以在一起工作。通俗的讲就是当我们已经有了一些类,而这些类不能满足新的需求,此时就可以考虑是否能将现有的类适配成可以满足新需求的类。适配器类需要继承或依…
暂无图片
编程学习 ·

SpringBoot

文章目录springboot的产生背景?spring boot pom依赖jar包的==@SpringBootApplication==Spring Boot 启动注解思维图**@SpringBootConfiguration**:**@EnableAutoConfiguration**:快速创建SpringBoot工程配置文件YML语法配置文件值获取@PropertySource&@ImportResource配置…
暂无图片
编程学习 ·

RPC框架正确的使用姿势

RPC框架-Thrift介绍RPC(Remote Procedure Call)远程过程调用,简单的理解是一个节点请求另一个节点提供的服务;本地过程调用:如果需要将本地student对象的age+1,可以实现一个addAge()方法,将student对象传入,对年龄进行更新之后返回即可,本地方法调用的函数体通过函数指…
暂无图片
编程学习 ·

哈夫曼编码

哈夫曼编码 输入一个字符串文本 #include <stdio.h> #include <stdlib.h> #include <string.h>#define cmax 0x3f3f3f3f // 宏定义一个较大的数,作为比较数据 #define cmaxsize 10000 // 宏定义数组的长度 // ---构建哈夫曼树 // ---定义哈夫曼…
暂无图片
编程学习 ·

jQuery 的实现原理

(function(window, undefined) {})(window); jQuery 利用 JS 函数作用域的特性,采用立即调用表达式包裹了自身,解决命名空间和变量污染问题 window.jQuery = window.$ = jQuery; 在闭包当中将 jQuery 和 $ 绑定到 window 上,从而将 jQuery 和 $ 暴露为全局变量
暂无图片
编程学习 ·

css3属性选择器

属性选择器 基本用法选择符 简介E[att] 选择具有att属性的E元素E[att=val] 选择具有att属性且属性值等于val的E元素E[att^=“val”] 匹配具有att属性、且值以val开头的E元素E[att$=“val”] 匹配具有att属性、且值以val结尾的E元素E[att*=“val”] 匹配具有att属性、且值中含有…
暂无图片
编程学习 ·

2.4-7、背包问题

7、背包问题 【问题描述】 简单的背包问题。设有一个背包,可以放入的重量为s。现有n件物品,重量分别为w1,w2…,wn,(1≤i≤n)均为正整数,从n件物品中挑选若干件,使得放入背包的重量之和正好为s。找到一组解即可。 【输入格式】 第一行是物品总件数和背包的载重量,第二行…
暂无图片
编程学习 ·

HDU3342 Legal or Not(拓扑排序)

HDU3342 Legal or Not(拓扑排序) Description ACM-DIY is a large QQ group where many excellent acmers get together. It is so harmonious that just like a big family. Every day,many “holy cows” like HH, hh, AC, ZT, lcc, BF, Qinz and so on chat on-line to ex…
暂无图片
编程学习 ·

项目实训——数据渲染数据引擎

项目实训——数据渲染数据引擎数据渲染layui卡片布局layui分页layui数据引擎遇到的问题 今天的任务就是要做出每个版块的页面。板块页面最重要就是数据的渲染。为了样式的统一,我继续使用layui,在这里用的是模板引擎laytpl。 数据渲染 layui卡片布局 为了美观,我使用了卡片式…
暂无图片
编程学习 ·

二进制与十进制转换工具类

package util;/*** 二进制工具类* * @author 谢辉* @time 2020.07.01**/ public class BinaryUtil {/*** 十进制数字转二进制* * @param num 十进制数字* @param strResult 结果容器,追加结果用,* @return 返回结果字符串*/public static String DecimalToBinary(Integ…
暂无图片
编程学习 ·

ELK详细安装部署

系统配置:CentOS7.6 4核4G ELK版本:7.7.1 elastic官网地址:https://www.elastic.co/cn/ elastic产品地址:https://www.elastic.co/cn/elastic-stack yum源地址:https://mirrors.tuna.tsinghua.edu.cn/elasticstack/yum 前言 日志主要包括系统日志和应用程序日志,运维和开…
暂无图片
编程学习 ·

互联网行业VS传统行业,哪碗饭更香?

这些年,网络发展速度越来越快,通过网络赚钱的项目也越来越多。但是,如果你去对这些项目进行分类的话,其实这些项目大致也就分为几种,赚钱的方式也大致相同。这个时代给我们提供了很多网上赚钱的机会。老实说,现在赚钱不一定非要去公司或工厂工作,何况在公司或工厂工作的…
暂无图片
编程学习 ·

非NC模式对接工行接口,工行返回的xml报文转json

第一次写博客,写得不好请见谅!公司本来有个旧项目是用PHP3.1开发的,结果现在增加了一个需求。项目要求:客户通过银行APP自助转账来入金到平台,平台则通过非NC方式对接工行接口出金。本来应该是没有我这边的事的,谁知最后开发的时候,工行的项目经理反馈说现在非NC模式不支…
暂无图片
编程学习 ·

node.js实现爬虫项目展示大作业

一、项目要求二、实现 1、用户可注册登录网站,非注册用户不可登录查看数据 登录页、注册页 <!DOCTYPE html> <html ng-app="login"> <head><meta charset="utf-8" /><title>Login</title><link rel="stylesh…
暂无图片
编程学习 ·

mui案例:导航栏 颜色渐变

mui导航栏 滚动渐变 代码参考 代码: <!DOCTYPE html> <html><head><meta charset="utf-8"><title>Hello MUI</title><meta name="viewport" content="width=device-width, initial-scale=1,maximum-scale=…
暂无图片
编程学习 ·

Python基础语法:print()、input()函数与变量

知识:print()、input()函数与变量————————————————————————————————————————1、print()与引号的使用print(This is a egg) #》》This is a egg print(This \s a egg) #》》Thiss a egg print("Thiss a egg") #可以打印&quo…