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).
Press Submit to check your solution.
Back to lesson: Practice: Sequence DP Problem Set