Ðề: Tìm dãy con của một dãy
Giải thuật thoạt xuất hiện trong đầu nên chưa chắc là tốt nhất:
1) Xây dựng đồ thị:
Xem mỗi phần từ ai của dãy là một đỉnh của đồ thị có hướng. Cạnh của đồ thị aiaj với (i < j). Trọng lượng cạnh là ai.
Lưu ý trong quá trình xây dựng đồ thị cần loại bỏ các ai >= s.
2) Áp dụng giải thuật LLoyd để tìm đường đi 2 đỉnh đồ thị. Sau đó in ra đường đi nào có độ dài s-d (với d là đỉnh cuối của đường đi).
__________________
Necessity is the mother of in(ter)vention.
Speak softly & carry a big stick.
My Technical Blog
|