LIQ spoj - Dãy con tăng dài nhất

Nguồn đề bài: http://vn.spoj.com/problems/LIQ/

1. Đề bài LIQ Dãy con tăng dài nhất

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.

2. Hướng dẫn LIQ SPOJ Dãy con tăng dài nhất

– Gọi F[i] là độ dài dãy con tăng dần dài nhất kết thúc tại i

– khởi tạo F[i]=1; (với i=1..n)

– F[i]=max(F[i],F[j]+1) (A[i]>A[j] ; i=1..n, j=1..i-1).

– nghiệm bài toán Max(F[i]) (i=1..n)

3. Code tham khảo LIQ SPOJ Dãy con tăng dài nhất

a. Code Pascal

const   fi='';
        nmax=1000;
type    data=longint;
var
        f:text;
        A,B:array[0..nmax+1] of data;
        n:data;

procedure docfile;
var     i,j:data;
begin
        assign(f,fi); reset(f);
        readln(f,n);
        for i:=1 to n do
                read(f,a[i]);
        close(f);
end;

function max(a,b:data):data;
begin
        if a>b then exit(a); exit(b);
end;

procedure qhd;
var     i,j,res:data;
begin
        res:=1;
        for i:=1 to n do
                begin
                        b[i]:=1;
                        for j:=1 to i-1 do
                                if A[i]>a[j] then
                                        b[i]:=max(b[i],b[j]+1);
                        res:=max(res,b[i]);
                end;
        writeln(res);
end;

begin
        docfile;
        qhd;
end.

b. code c++

#include <stdio.h>
#include <algorithm>
using namespace std;
#define nmax=1000
int n;
int a[1000], f[1000];
int main()
{
    scanf("%d",&n);
    int i,j;
    for (i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
        f[i]=1;
    }
    for (i=1; i<=n; i++)
    {
        for (j=i+1; j<=n; j++)
        {
            if (a[i]<a[j]) f[j]=max(f[i]+1,f[j]);
        }
    }
    int res=0;
    for (i=1; i<=n; i++) res=max(res,f[i]);
    printf("%d",res);
    return 0;
}

LIQ spoj – Dãy con tăng dài nhất