Editorial for Gộp dãy toàn số 1
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
- Cách trâu: Độ phức tạp \(O(n^2)\): Đếm số lượng số 1 trong dãy. Giả sử là \(x\). Ta cần tìm dãy con có độ dài \(x\) với số lượng số 1 nhiều nhất. Như vậy, số lượng phép tráo đổi cần thiết sẽ là số lượng số 0 trong dãy vừa tìm có độ dài \(x\) ở trên.
- Cách 2. Độ phức tạp \(O(n)\). Cải tiến từ cách trâu ở trên, sử dụng kĩ thuật dịch cửa sổ (sliding window). Ta gọi preCount là mảng lưu số lượng phần từ 1 trong mỗi dãy con - tính bằng kĩ thuật cộng dồn. Tiếp tục sử dụng kĩ thuật sliding window tìm đoạn con kích thước x có số lượng 1 nhiều nhất.
Comments