Hướng dẫn cho Trồng hoa
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Gọi :
- \(f[i]\) là vị trí nhỏ nhất mà đoạn (\(f[i], i\)) là một khóm hoa đạt tiêu chuẩn
- \(g[i\)] là độ dài lớn nhất của khóm hoa đạt tiêu chuẩn từ nằm trong đoạn (\(1, i\))
Để tính \(f[i]\) tốn \(O(n ^ 2)\), chúng ta có thể giảm đpt xuống \(O(nlog)\) bằng IT hoặc RMQ nhưng time sẽ hơi chặt, \(O(n)\) nếu dùng deque
=> \(answer = max(i - f[i] + 1, g[f[i] - 1])\);
Bình luận