MAXSUM – Dãy con có tổng lớn nhất

Buổi 21 — DP 1D cổ điển dynamic-programming
Points
25
AC Rate
66.7%
Time limit
1.5 s
Memory limit
256M
Group
dp
Submissions

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$.

Draft saved