Tutorial — Thành Tích

Trận đấu thứ $i$ ($i > 1$) chỉ được tính là trận đấu ấn tượng nếu điểm số $a_i$ lớn hơn tất cả hoặc nhỏ hơn tất cả các điểm số trong đoạn tiền tố từ $a_1$ đến $a_{i-1}$.

Thay vì so sánh $a_i$ với tất cả $i - 1$ phần tử trước đó, ta chỉ cần so sánh $a_i$ với giá trị lớn nhất $M_{i-1}$ và giá trị nhỏ nhất $m_{i-1}$ của đoạn tiền tố đó.

Duyệt qua dãy từ trận đấu thứ $2$ đến $n$, duy trì hai biến lưu trữ điểm số cao nhất và thấp nhất đã gặp để kiểm tra và cập nhật biến đếm trong thời gian $O(n)$.