The substring and

The time limit :5000 ms  |  Memory limit :65535 KB
difficulty :3
 
describe
Given an integer sequence {a 1,a 2...,a n}, Find continuous nonempty substrings {a x,a x+1,...,a y}, Make the sum of the subsequence maximum , among ,1<=x<=y<=n.
 
Input
The first line is an integer N(N<=10) Number of groups representing test data )
The first row of each set of test data is an integer n It means that there are in a sequence n It's an integer , In the next line are n It's an integer I(-100=<I<=100), Represents all the elements in a sequence .(0<n<=1000000)
Output
For each group of test data output and the sum of the largest continuous substring .
The sample input
1
5
1 2 -1 3 -2
Sample output
5


The key :if(sum<0) sum=0;
 #include<stdio.h>
int main()
{
int t,n,i,k,max,sum;
scanf("%d",&t);
while(t--)
{
sum=;max=-;
scanf("%d",&n);
for(i=;i<n;i++)
{
scanf("%d",&k);
sum+=k;
if(sum>max)
max=sum;
if(sum<)
sum=;
}
printf("%d\n",max);
}
return ;
}

nyoj 44 The substring and More articles on simple dynamic programming

  1. nyoj 44 The substring and

    The substring and The time limit :5000 ms  |  Memory limit :65535 KB difficulty :3   describe Given an integer sequence {a1,a2...,an}, Find continuous nonempty substrings {ax,ax+1,...,ay}, So that the sum of the subsequence is the most significant ...

  2. nyoj 44

    //nyoj 44 // Same as above , Finding the sum of substrings , But the code is very concise ..... The time complexity is n #include <iostream> using namespace std; int ma ...

  3. nyoj 284 Tanks war Simple search

    Topic link :http://acm.nyist.net/JudgeOnline/problem.php?pid=284 The question : In a given graph , Iron wall , The river cannot go , If the brick wall goes away , Spend more time 1, Ask from the beginning to the end at least ...

  4. Simple dynamic programming —— Three inverses O(N^2) solution !

    [ Algorithm ] Simple dynamic programming —— Three inverses O(N^2) solution ! Problem description : The definition of triple inverse number : Give a sequence of numbers A[0,1,....N-1]), When i<j<k And A[i]>A[j]>A[k] when , Referred to as ai ...

  5. NYOJ 44 Strings and ( Maximum string sum linear dp)

    Topic link : http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=44 The substring and The time limit :5000 ms  |  Memory limit :65535 KB difficulty :3 ...

  6. UVA - 11584 Dividing palindrome string substring of string ; Simple dp

    /** link :http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=34398 UVA - 11584 Dividing palindrome string substring of string : Simple ...

  7. nyoj subject 44 The substring and

    The substring and The time limit :5000 ms  |  Memory limit :65535 KB difficulty :3   describe Given an integer sequence {a1,a2...,an}, Find continuous nonempty substrings {ax,ax+1,...,ay}, So that the sum of the subsequence is the most significant ...

  8. Written test algorithm problem (44): brief introduction - Dynamic programming (Dynamic Programming)

    issue : Dynamic programming (Dynamic Programming) analysis : DP It is mainly used to solve the overlapping subproblem (Overlapping Subproblems) Optimization problem of , The basic strategy is to decompose the original problem into similar subproblems , ...

  9. Leetcode(5)- Longest text substring ( Including dynamic programming and Manacher Algorithm )

    Given a string  s, find  s  The longest palindrome substring in . You can assume  s  The maximum length of is 1000. Example 1: Input : "babad" Output : "bab" Be careful : &quo ...

Random recommendation

  1. android Dynamic setting of control width and height

    Android Use it directly in the code setWidth() and setHeight() It's no use setting the width and height . The solution is change to the use of sth. setLayoutParams() Method Such as setting width and height, content adaptation : setLayout ...

  2. In depth understanding of java virtual machine 【Java Class Class file structure 】

    Java Language claims to be written once from its birth , Cross platform features that run everywhere , Its implementation principle is that the source code file is not directly compiled into machine instructions , It's compiled as Java Bytecode files that virtual machines can recognize and run (Class Class file ,*.class), Bytecode ...

  3. Linux Install Song typeface and Microsoft YaHei font

    Recent work itext Generate pdf stay windows There is no Chinese garbled code in the environment linux Chinese garbled under , open pdf see pdf code , And the code displayed , It is found that there is no corresponding code . The reason is the use of Song Ti and Microsoft YaHei in linux Ring ...

  4. 【 turn 】【CDC Turn over customers 】 Mobile App Practical guide to testing

      translator's note : This paper starts from the perspective of testers , Put forward 100 Multiple tests are moving App Issues to be considered in the process . It doesn't matter if you're a tester . Development . Product manager or interaction designer , Moving App When developing , These questions are of great reference value . Me and Queen ...

  5. Spread Custom diagonal cellType Source code : DiagonalCellType

    Abreast of the times SpreadWinform Up to 24 Kind of CellType type , The next one is 2 A new blog post is added GcTextBoxCellType and GcDateTimeCellType The cell format is explained in detail . & ...

  6. vs2010 Of VCVARS32.BAT The position of

    1. C:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\bin\vcvars32.bat 2. ZC:vs08 and vs2010 After installed , ...

  7. commonjs Detailed explanation

    marked here a well written artical http://javascript.ruanyifeng.com/nodejs/module.html

  8. UVA1386 【Cellular Automaton】 Answer key

    Topic :UVA1386 Cellular Automaton Matrix multiplication + Fast power method : This is a bare and a bit complicated moment multiplication fast power that needs to be optimized , So I recommend you to do the following Luogu exercises first : ( Yes , It's almost a multiple experience problem ...

  9. Let the new version Chrome Support local cross domain request debugging

    1. Create a Chrome Startup shortcut for : 2. Right click shortcut properties , And then behind the target path , Add the following parameters : --disable-web-security --user-data-dir="e:\ ...

  10. thinkphp5 Alipay mobile phone payment interface is integrated in the website.

    Today with thinkphp5 Using Alipay mobile phone payment interface as an example . One . Create basic page pay/alipay_wap_submit.php( Start order creation ) <!DOCTYPE html> <htm ...