Cho
một dãy gồm N số nguyên (1 ≤ N ≤ 30000). Hãy tìm dãy con tăng dài nhất trong
dãy đó. In ra số lượng phần tử của dãy con. Các số trong phạm vi longint.
Input
- Dòng đầu tiên gồm số nguyên N.
- Dòng thứ hai gồm N số mô tả dãy.
Output
Gồm
một số nguyên duy nhất là đáp số của bài toán
Example
Input:
5
2 1 4 3 5
Output:
3==================
Hướng dẫn: cái này là tui chôm chỉa trong cuốn "Một số vấn đề đáng chú ý trong tin học" nằm ở trang 137 (tác giả có viết code luôn ^^);
**** Nói theo kiểu "cây nhà lá vườn" mình thì vầy nè:
Trong đó có cái mảng H nó chứa chỉ số của các phần tử trong dãy con tăng. res là độ dài của nó...
Khời tạo mảng H với phần tử đầu tiên giả sử là A[1]...
Chạy từ 2 tới n xét từng phần từ một....
phần tử thứ i, ta lại xét 3 trường hợp sau đây:
1 ---------> nếu A[i] < A[ H[1] ] thì H[1]:=i, cái điều kiện 1 này dễ hiểu thôi, H[1] là chỉ số phần tử đầu tiên trong dãy con tăng của chúng ta, vậy thì nó phải nhỏ nhứt, mà cái phần tử thứ i này nó còn nhở hơn phần tử đầu nữa thì phải gán lại thôi....
2 ---------> nếu A[i] > A[H[res]] thì INC(res) và gán H[res]:=i; , cái này cũng dễ hiểu nữa, H[res] thì chỉ số thằng cuối cùng trong dãy con tăng, tất nhiên nó phải là thằng lớn nhứt, xét tới ông A[i], ổng còn lớn hơn cả phần tử thứ H[res] thì kết nạp ổng vô dãy con tăng luôn....
3 --------> nảy giờ mình giải quyết cái đầu với cái cuối, giờ tới cái chính giữa, keke, cái này căng thẳng nè, xài chặt nhị phân
đó là trường hợp mà phần tử A[i] không < A[H[1]] mà cũng không > A[h[res]] luôn........mình sẽ giải quyết nội bộ cái mảng H, chặt mảng H ra để tìm vị trí thích hợp gắn ông A[i] vô..................cơ bản là vậy nè, ta sẽ chặt nhị phân tìm cái thằng đầu tiên trong dãy con tăng (hiện có) lớn hơn giá trị ta đang xét, nói lại là tìm "phần tử ĐẦU TIÊN lớn hơn phần tử đang xét", rồi ta gán lại "phần tử ĐẦU TIÊN lớn hơn phần tử đang xét" đó đó thành phần tử đang xét.......
Rồi xong, in RES ra
P.S: nói chung cách chặt nhị phân khó nghĩ lắm!! Chúc các bro AC bài này
