[Spoj] Dãy con tăng dài nhất – LIQ

Đề bài và test: link

Cho một dãy số nguyên gồm N phần tử A[1], A[2], … A[N].
Biết rằng dãy con tăng đơn điệu là 1 dãy A[i1],… A[ik] thỏa mãn
i1 < i2 < … < ik và A[i1] < A[i2] < .. < A[ik]. Hãy cho biết dãy con tăng đơn điệu dài nhất của dãy này có bao nhiêu phần tử?
Download test và solution (C/C++, Pascal) tại đây.
Input
Dòng 1 gồm 1 số nguyên là số N (1 ≤ N ≤ 1000).
Dòng thứ 2 ghi N số nguyên A[1], A[2], .. A[N] (1 ≤ A[i] ≤ 10000).
Output
Ghi ra độ dài của dãy con tăng đơn điệu dài nhất.
Ví dụ
Input:
6
1 2 5 4 6 2
Output:
4
Giải thích test ví dụ: Dãy con dài nhất là dãy A[1] = 1 < A[2] = 2 < A[4] = 4 < A[5] = 6, độ dài dãy này là 4.

Trước tiên dùng 1 mảng b để đánh dấu độ dài dãy tăng tại vị trí b[i] bất kỳ. Một biến max đánh dấu độ dài dãy tăng dài nhất. Ban đầu b[i] = 1 với mọi i, max = 1.
Duyệt dãy a với 1 vòng for.
Trong khi duyệt, tại mỗi phần tử ta duyệt ngược lại đầu dãy. Nếu b[i] <= b[j] và a[i] > a[j] và b[i] <= max thì ta tăng b[i] lên = b[j] + 1; Kiểm tra và gán lại max.
VD:
Ban đầu
a[] : 1 2 5 4 6 2
b[] : 1 1 1 1 1 1

Duyệt lần 1: (i=1)
a[1] = 2. Duyệt từ a[0] về a[0].
ta thấy b[1] <= b[0] và a[1] > a[0] và b[1] <=max => b[1] = b[0] + 1 = 2, max = b[1] = 2.
Duyệt lần 2: (i=2)
a[2] = 5. Duyệt từ a[1] về a[0].
+/ Xét a[1], ta thấy b[2] <= b[1] và a[2] > a[1] và b[2] <=max => b[2] = b[1] + 1 = 3, max = b[2] = 3.
+/ Xét a[0], b[2] =3 > b[0] => không làm gì.
Duyệt lần 3: (i=3)
a[3] = 4. Duyệt từ a[2] về a[0].
+/ Xét a[2], ta thấy b[3] <= b[2] nhưng a[3] < a[2] => không làm gì
+/ Xét a[1], ta thấy b[3] <= b[1] và a[3] > a[1] và b[3] <=max => b[3] = b[1] + 1 = 3, max giữ nguyên.
+/ Xét a[0], b[3] =3 > b[0] => không làm gì.
Duyệt lần 4: (i=4)
a[4] = 6. Duyệt từ a[3] về a[0].
+/ Xét a[3], ta thấy b[4] <= b[3] và a[4] > a[3] và b[4] <=max => b[4] = b[3] + 1 = 4, max = b[4] = 4.
+/ Xét a[2], ta thấy b[4] = 4 > b[2] => không làm gì.
+/ Xét a[1], ta thấy b[4] = 4 > b[1] => không làm gì.
+/ Xét a[0], ta thấy b[4] = 4 > b[0] => không làm gì.
Duyệt lần 5: (i=5)
a[5] = 2. Duyệt từ a[4] về a[0].
+/ Xét a[4], ta thấy b[5] <= b[4] nhưng a[5] < a[4] => không làm gì
+/ a[3], a[2], a[1] tương tự
+/ Xét a[0], ta thấy b[5] <= b[0] và a[5] > a[0] và b[5] <=max => b[5] = b[0] + 1 = 2, max giữ nguyên.
Vậy ta có:
a[] : 1 2 5 4 6 2
b[] : 1 2 3 3 4 2
max = 4.