Đoạn Con Liên Tiếp Có Tổng Lớn Nhất (Kadane)

Arrays Dynamic Programming
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Submissions
Đề bài

Cho mảng A gồm N số nguyên (có thể chứa cả số âm và số dương). Hãy tìm tổng lớn nhất của một đoạn con liên tiếp khác rỗng trong mảng.

Dữ liệu vào (Input)
  • Dòng 1: Số nguyên dương N (1 ≤ N ≤ 2 × 10^5).
  • Dòng 2: N số nguyên A[1], A[2], ..., A[N] (-10^9 ≤ A[i] ≤ 10^9).
Dữ liệu ra (Output)
  • In ra một số nguyên duy nhất là tổng đoạn con liên tiếp lớn nhất.
Ví dụ mẫu
Sample Input 1
8
-1 2 4 -3 5 2 -5 2
Sample Output 1
10
Sample Input 2
3
-8 -3 -6
Sample Output 2
-3
Gợi ý thuật toán

Thuật toán Kadane O(N): Duy trì cur = max((long long)A[i], cur + A[i]) và best = max(best, cur).

Draft saved