子串和

描述

给定一整型数列{a₁,a₂...,a_n}，找出连续非空子串{a_x,a_x+1,...,a_y}，使得该子序列的和最大，其中，1<=x<=y<=n。

输入

第一行是一个整数N(N<=10)表示测试数据的组数）

每组测试数据的第一行是一个整数n表示序列中共有n个整数，随后的一行里有n个整数I(-100=<I<=100)，表示数列中的所有元素。(0<n<=1000000)

输出

对于每组测试数据输出和最大的连续子串的和。

样例输入

1

5

1 2 -1 3 -2

样例输出

5

提示

输入数据很多,推荐使用scanf进行输入

来源

经典问题

这种题最近总是遇到，就是一个无脑加，然后一个比较和判断

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

int a[1000100];

int main()

{

	int t;

	scanf("%d",&t);

	while(t--)

	{

		memset(a,0,sizeof(a));

		int n;

		scanf("%d",&n);

		for(int i=0;i<n;i++)

		scanf("%d",&a[i]);

		int sum,max;

		sum=max=a[0];

		for(int i=1;i<n;i++)

		{

			sum+=a[i];

			if(sum<0)

			sum=0;

			if(sum>max)

			max=sum;

		}

		printf("%d\n",max);

	}

	return 0;

}

最新文章

1. 利用powerDesigner16.5连接oracle数据库并自动生成表结构图
2. POJ 1061
3. Java中如何解决double和float精度不准的问题
4. python模块之codecs
5. 【测试】模拟一个全表扫描的sql，对其进行优化走索引，并且将执行计划稳定到baseLine。
6. JS代码的简单重构与优化
7. EasyBCD安装CentOS双系统
8. 前台 添加引用 iis文件路径
9. 疯狂VirtualBOX 实战讲学录:小耗子之VirtualBOX修炼全程重现
10. 如何利用多核CPU来加速你的Linux命令 — awk, sed, bzip2, grep, wc等(转)
11. PHP第七课 使用方法数组2
12. 关于github在客户端不小心删除新仓库，重建后无法上传解决方法
13. input依次输入密码
14. python importlib动态导入模块
15. 从零开始学习PYTHON3讲义（十五）让画面动起来
16. （转载）深度剖析 | 可微分学习的自适配归一化 (Switchable Normalization)
17. 我的第一个Java程序和Java简介
18. SpringMVC框架06——文件上传与下载
19. Error -27780: Connection reset by peer: socket write error
20. 10个基于 JavaScript 的 WYSIWYG 编辑器

热门文章

1. ［转］深入javascript——原型链和继承
2. 使用 CSS 追踪用户
3. JDBC的详细使用
4. 【Linux】连接CRT
5. 使用cookies查询商品详情
6. c#使用RSA进行注册码验证
7. php实现非对称加密
8. ASP.NE 上传文件控件
9. javeee 字节Buffered
10. HDU 4405 Aeroplane chess(概率dp，数学期望)