Dãy con tăng dài nhất. O(N^2)

Vấn đề:
Cho dãy số a1,a2,..an. Dãy con là một dãy sao cho ai1,ai2,...,aij; trong đó i1 < i2 < ij và ai1,ai2,...,aij phải có mặt trong dãy a1,a2,...,an ban đầu. Hãy tìm dãy con tăng dài nhất.
Lời giải tham khảo:
Gọi f[i] là dãy con tăng dài nhất khi xét dãy a1,a2,...,ai mà  ai là phần tử cuối cùng của dãy con.

• f[0] = 0;
• Tìm j<i sao cho f[j] lớn nhất mà a[j] < = a[i]. Nếu không tìm thấy thì j =0;
• f[i] = f[j] + 1
•  result = max (F[i]), i=1,...,N.

Độ phức tạp thuật toán O(N^2).
Áp dụng các bạn giải bài tập sau trên hệ thống vnoi:
Link: http://vnoi.info/index.php?option=com_voj2&page=problem&problem=LIQ#tab_statement

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[i₁],... A[i_k] thỏa mãn
i₁ < i₂ < ... < i_k và A[i₁] < A[i₂] < .. < A[i_k]. 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.

Gợi ý: Sử dụng phương pháp Quy Hoạch Động. F[i]: Độ dài dãy con đơn điệu tăng dài nhất mà phần tử cuối cùng là số A[i] này.

Code:
DevC:

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int N;
int a[1001];
int f[1001];

int main()
{
scanf("%d",&N);
for(int i=1;i<=N;i++)
scanf("%d",&a[i]);
f[1] = 1;
for(int i=2;i<=N;i++)
{
int temp = 0;
for(int j=1;j<i;j++)
if(a[j]<a[i]&&temp<f[j]) temp = f[j];
f[i] = temp + 1;
}
int res = -1;
for(int i=1;i<=N;i++)
{
res = max(res,f[i]);
}
printf("%d",res);
//system("pause"); dừng lại để xem kết quả.
return 0;
}

Free pascal:

var

    N,i,res,temp,j:longint;

    a,f:array[1..1001]of longint;

begin

    readln(N);

    for i:=1 to N do

        read(a[i]);

    f[1]:=1;

    for i:=2 to N do

        begin

            temp:=0;

            for j:=1 to i-1 do

                if((a[j]<a[i]) and (f[j]>temp)) then

                    temp:=f[j];

            f[i]:=temp+1;

        end;

    res:=0;

    for i:=1 to N do

        if(res<f[i]) then res:=f[i];

    writeln(res);

end.

Tham khảo: http://en.wikipedia.org/wiki/Longest_increasing_subsequence