Đề 9 - E. Xây nhà trong thành phố
Một kiến trúc sư trưởng được giao nhiệm vụ quy hoạch đường chân trời (skyline) cho một thành phố mới. Có N tòa nhà đã được cấp phép xây dựng theo một thứ tự cố định dọc theo một con đường. Tòa nhà thứ i có độ cao là hᵢ.
Để tạo ra một cảnh quan đẹp mắt, kiến trúc sư muốn chọn ra một nhóm các tòa nhà từ N tòa nhà đã cho. Các tòa nhà được chọn phải thỏa mãn điều kiện: khi nhìn từ đầu này đến đầu kia của con đường, tòa nhà đứng sau phải cao hơn tòa nhà đứng ngay trước nó trong nhóm được chọn.
Giữ nguyên vị trí tương đối của các tòa nhà, hãy giúp kiến trúc sư tìm ra số lượng tòa nhà tối đa có thể chọn để tạo thành một skyline "cao dần" đẹp mắt.
Dòng đầu tiên là số nguyên N, tổng số tòa nhà được đề xuất. (1 ≤ N ≤ 10 12)
Dòng thứ hai gồm N số nguyên là độ cao của các tòa nhà theo thứ tự (1 ≤ N ≤ 10 12) .
Một số nguyên duy nhất là số lượng tòa nhà tối đa có thể chọn.
Đầu vào:
5
2 1 4 3 5Đầu ra:
3Giải thích:
Từ 5 tòa nhà có độ cao [2, 1, 4, 3, 5], kiến trúc sư có thể chọn ra tối đa 3 tòa nhà để tạo thành một dãy cao dần. Một cách chọn là các tòa nhà có độ cao [1, 3, 5].
Ta có thể tìm thấy dãy tòa nhà là 1, 3, 5. Dãy này có 3 tòa nhà. Lưu ý rằng có thể có nhiều dãy tòa nhà dài nhất khác nhau (ví dụ: 1, 4, 5 hoặc 2, 4, 5), nhưng tất cả chúng đều có cùng độ dài là 3.
Comments