Skip to main content

Practice · 2 of 4

Dãy ngoặc dài nhất

CHALLENGE
Difficulty: intermediate+25 XP

**Bài toán.** Xâu chỉ gồm '(' và ')' (độ dài ≤ 10^6). In độ dài dãy ngoặc hợp lệ LIÊN TIẾP dài nhất. Stack chỉ số: đẩy chỉ số '('; gặp ')' pop — nếu stack rỗng, đẩy chỉ số này làm "hàng rào"; ngược lại độ dài = i − chỉ số đỉnh stack. Khởi tạo stack với −1 làm hàng rào gốc. Cái bẫy kinh điển: đếm SỐ CẶP khớp ở bất kỳ đâu — bỏ điều kiện liên tiếp (vd "()((" có 2 cặp nhưng dãy liên tiếp dài nhất là 2).

Back to lesson: Practice: Contest Problem Set