Link Sub: http://www.spoj.com/PTIT/problems/BCLIQ/
Người Gửi: Dương Lee
- Problem:
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ử?
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.
Example:
Ghi ra độ dài của dãy con tăng đơn điệu dài nhất.
Input
6
1 2 5 4 6 2
Output:
4
- Solution:
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.Áp dụng QHĐ xây dựng hàm F[i] = max (F[i], F[j]+1) (j:=i-1 -> 1 && A[j]<A[i])
=> max (F[]);
Với test trên ta có F[] = {1, 2, 3, 3, 4, 2}
Có nghĩa là: tại A[i] ta tìm các A[j] sao cho A[j]<A[i] mà tại đó độ dài dài nhất của dãy con tăng là F[j] ta thu được F[i] = F[j]+1; (chọn F[i] max)
Độ phức tạp O(N^2)
- Code:
C++:
https://ideone.com/NukN69
#include <iostream>
#include <algorithm>
using namespace std;
int main ()
{
int n;
cin>>n;
long arr[1003];
long F[1003];
for (int i=1; i<=n; i++)
cin>>arr[i];
arr[0] = 0;
F[0] = 0;
for (int i=1; i<=n; i++)
{
F[i] = 1;
for (int j=i-1; j>=1; j--)
{
if (arr[i]>arr[j])
{
F[i]=max(F[i], F[j]+1);
}
}
}
long dmax = 1;
for (int i=1; i<=n; i++)
if (F[i]>=dmax)
dmax = F[i];
cout<<dmax;
return 0;
}