Tổng dãy con lớn nhất
View as PDF
Submit solution
Points:
0.11 (partial)
Time limit:
1.0s
Memory limit:
256M
Input:
stdin
Output:
stdout
Author:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho một dãy ~A~ gồm ~n~ phần tử ~A_1, A_2, \ldots, A_n~. Tìm dãy con liên tiếp có tổng lớn nhất của ~A~.
Dãy con liên tiếp của ~A~ là đoạn liên tục, gồm các phần tử nằm liền nhau của ~A~. Ví dụ cho dãy ~A = [6, -1, 2, 8, -4]~ thì dãy ~B = [-1, 2, 8]~ là một dãy con liên tiếp của dãy ~A~. Còn dãy ~C = [6, 2, -4]~ không là một dãy con liên tiếp của ~A~.
Input
Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 10^5~) — độ dài dãy ~A~.
Dòng thứ hai gồm ~n~ số nguyên mô tả dãy ~A~ (~|A_i| \le 10^9~).
Output
Gồm một dòng duy nhất chứa giá trị dãy con liên tiếp có tổng lớn nhất của dãy ~A~.
Sample Input 1
6
-1 3 -1 2 1 -5
Sample Output 1
5
Notes
Dãy con liên tiếp có tổng lớn nhất là ~A_2 + A_3 + A_4 + A_5 = 3 - 1 + 2 + 1 = 5~
Comments
ao ma canada nobita an ba ba mua tren lazada vay ts