Skip to main content

Practice · 5 of 5

Đoạn không âm dài nhất

CHALLENGE
Difficulty: intermediate+25 XP

**Bài toán.** Dãy n số nguyên. In độ dài đoạn LIÊN TIẾP dài nhất mà TỔNG ≥ 0. Không có → in 0. **Ràng buộc:** 1 ≤ n ≤ 200 000; |a_i| ≤ 10^9. Tiền tố P: đoạn (l, r] tổng ≥ 0 ⇔ P[r] ≥ P[l] — giữ danh sách ứng viên P GIẢM NGẶT (prefix-minima) và nhị phân tìm l nhỏ nhất cho mỗi r: O(n log n).

Back to lesson: Practice: Sequence DP Problem Set