Dãy con liên tục có tổng lớn nhất
Submit solution
Points:
3 (partial)
Time limit:
1.0s
Memory limit:
98M
Author:
Problem types
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG
Cho một dãy số nguyên a1,a2 … an, một dãy con liên tục được sinh ra bằng cách lấy các phần tử liền nhau nào đó trong dãy. Nhiệm vụ của bạn tìm tổng lớn nhất của tất cả các dãy con liên tục sinh ra bởi dãy số nguyên ban đầu.
Input
- Dòng đầu là số nguyên dương N (1<=N<=10^5)
- Dòng 2 là N số nguyên có giá trị (-1000<=ai<=1000) mỗi số cách nhau bằng ít nhất 1 khoảng trống
Output
- Một số nguyên là tổng lớn nhất
Ví dụ 1
Input
7
3 -5 2 -1 4 -6 2Output
5Giải thích: tổng lớn nhất là 2+(-1)+4
Ví dụ 2
Input
7
3 -5 -2 -1 4 -6 2Output
4Giải thích: tổng lớn nhất là mỗi số 4
Comments
Kadane Algorithm