trang chủ / bài tập / cowrow / lời giải

Dãy bò dài nhất

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả:

huunguyen

Lời giải: Dãy bò dài nhất

Hướng tiếp cận

Brute-force: thử loại từng giống riêng biệt, tìm đoạn cùng giống dài nhất sau khi loại.

Nhận xét quan trọng

Khi loại giống $b$ , các bò thuộc giống $b$ được bỏ qua — không phá vỡ tính liên tiếp của các bò xung quanh.
$N \leq 1000$ và số giống phân biệt $\leq N$ , nên $O (N^{2})$ đủ nhanh.

Thuật toán

Với mỗi giống $b$ phân biệt:

Duyệt qua dãy, bỏ qua các bò thuộc giống $b$ .
Đếm đoạn liên tiếp dài nhất các bò cùng giống.
Cập nhật đáp án.

Độ phức tạp

Thời gian: $O (N^{2})$
Bộ nhớ: $O (N)$

Bình luận

Không có bình luận tại thời điểm này.