Mảng con có tổng lớn nhất

Tác giả:

Dạng bài

Ngôn ngữ cho phép

Assembly, Awk, C, C#, C++, Clang, Cobol, D, ~~Groovy~~, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, ~~Swift~~

Điểm: 1100 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho mảng \(A\) gồm \(N\) số nguyên (có thể chứa số âm). Hãy tìm đoạn con liên tiếp (subarray) có tổng lớn nhất trong mảng.

Input

Dòng 1: Số nguyên dương \(N\) (\(1 \le N \le 2 \cdot 10^5\)).
Dòng 2: \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(|A_i| \le 10^9\)).

Output

Một số nguyên duy nhất là tổng lớn nhất tìm được.

Example

Test 1

Input

8
-2 -5 6 -2 -3 1 5 -6

Output

Note

Đoạn con có tổng lớn nhất là \(\{6, -2, -3, 1, 5\}\). Tổng \(= 6 + (-2) + (-3) + 1 + 5 = 7\).

Scoring

Subtask \(1\) (\(40\%\) số điểm): \(N \le 1000\).
Subtask \(2\) (\(60\%\) số điểm): \(N \le 2 \cdot 10^5\).

Bình luận

Tải bình luận...

Không có bình luận nào.