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 2

Output

5

Giải thích: tổng lớn nhất là 2+(-1)+4

Ví dụ 2

Input

7
3 -5 -2 -1 4 -6 2

Output

4

Giải thích: tổng lớn nhất là mỗi số 4


Comments


  • 8
    COKE  commented on May 25, 2020, 2:50 p.m.

    Kadane Algorithm