MAXSUM – Dãy con có tổng lớn nhất
Points
25
AC Rate
66.7%
Time limit
1.5 s
Memory limit
256M
Group
dp
Cho dãy số nguyên gồm $n$ phần tử $A = [A_1, A_2, \dots, A_n]$. Dãy số có thể chứa cả các số nguyên âm.
Hãy tìm một đoạn con liên tiếp $A[i \dots j]$ ($1 \le i \le j \le n$) sao cho tổng các phần tử trong đoạn con này đạt giá trị lớn nhất (Bài toán Kadane).
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên dương $n$ ($1 \le n \le 10^6$).
- Dòng thứ hai chứa $n$ số nguyên $A_1, A_2, \dots, A_n$ ($-10^9 \le A_i \le 10^9$).
Dữ liệu ra
- In ra một số nguyên duy nhất là tổng lớn nhất của một đoạn con liên tiếp trong dãy.
Giới hạn
- Subtask 1 (30% số điểm): $n \le 1000$.
- Subtask 2 (70% số điểm): $n \le 10^6$.
Ví dụ
Đầu vào:
6
-2 3 4 -1 5 -3
Đầu ra:
11
Giải thích: Đoạn con có tổng lớn nhất là $[3, 4, -1, 5]$ với tổng bằng $3 + 4 + (-1) + 5 = 11$.
Community Discussion