首页
登录 | 注册

nyoj 题目44 子串和

子串和

时间限制:5000 ms  |  内存限制:65535 KB
难度:3
 
描述
给定一整型数列{a1,a2...,an},找出连续非空子串{ax,ax+1,...,ay},使得该子序列的和最大,其中,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进行输入
动态规划经典题目,代码如下
 1 #include <cstdio>
 2 #include <iostream>
 3 
 4 using namespace std;
 5 int num[1000006];
 6 
 7 int main(int argc, char const *argv[])
 8 {
 9     int n;
10     scanf("%d",&n);
11     while(n--) {
12         int m;
13         scanf("%d",&m);
14         for(int i = 0; i < m; i++) {
15             scanf("%d",&num[i]);
16         }
17         int ans = -1002;
18         int sum = 0;
19         for(int i = 0; i < m; i++) {
20             sum = max(sum+num[i],num[i]);
21             ans = max(ans, sum);
22         }
23         printf("%d\n", ans);
24     }
25     return 0;
26 }

 


相关文章

  • Npoi简单读写Excel
    什么是NPOI ? 简而言之,NPOI就是可以在没有Office的情况下对Word或Excel文档进行读写等操作. 使用方式 : 1.准备NPOI的dll文件 下载链接:https://npoi.codeplex.com/releases ...
  • python接口自动化(二十三)--unittest断言——上(详解)
    简介 在测试用例中,执行完测试用例后,最后一步是判断测试结果是 pass 还是 fail,自动化测试脚本里面一般把这种生成测试结果的方法称为断言(assert).用 unittest 组件测试用例的时候,断言的方法还是很多的,下面介绍几种常 ...
  • 计算机基础 01 计算机基础之编程 02 计算机组成原理 03 计算机操作系统 04 编程语言分类 Python解释器 05 Python和Python解释器 06 执行Python程序的两种方式 07 Python集成开发环境 变量 08 ...
  • Day1----Python学习之路笔记(1)
    学习路线 Day1 Day2 Day3 Day4 Day5 ...待续 一.了解开发语言 1.高级语言:Python,Java,C++,C#,PHP,JS,Go,Ruby,SQL,Swift,Perl,Objective-C,R等等: 2. ...

2019 cecdns.com webmaster#cecdns.com
12 q. 0.066 s.
京ICP备10005923号