Kiểm Tra Đầu Vào Lớp Chuyên Tin – VCoderLog

Sep 10, 2026, 21:59 – 21:59 (01:30:00) Live
Time Remaining 328 days 23:59:27
My Score
0 / 85
Rank
- / 1

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

25 points 1.5 s 256 MB b21-dp1d dynamic-programming

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

Sample Test 1
AC 3 ms 1.2 MB
Sample Test 2
AC 2 ms 1.1 MB
Sample Test 3
AC 3 ms 1.3 MB