Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|
Nộp bài Các bài nộp Làm tốt nhất PDF Về danh sách bài

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

Cho dãy N số nguyên A1, A2, ..., An. Tìm dãy con tăng dài nhất

Input

  • Dòng 1 chứa giá trị N <= 100
  • Dòng 2 chứa N số nguyên A1, A2, ..., An

Output

  • Dòng 1 chứa độ dài dãy con tăng dài nhất
  • Dòng 2 chứa các phần tử trong dãy con đó

Example

Input:
9
5 1 4 2 3 9 7 8 6
Output:
5
1 2 3 7 8 
Submit solution!
Được gửi lên bởi:Vương Trung Hiếu Nghĩa
Ngày:2016-01-31
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C++ 4.3.2 CPP CPP14 PAS-GPC PAS-FPC
hide comments
2016-02-19 02:43:40
#include<bits/stdc++.h>
using namespace std;
int n,a[1003],f[1003],maxx = 1,b[1001];
int main()
{
cin >> n;
for(int i=1;i<=n;i++)cin >> a[i];

f[1] = 1;
f[0] = 0;
a[0] = -1e9;
for(int i=2;i<=n;i++)
{
for(int j=0;j<=i-1;j++)
{
if(a[i] > a[j])f[i] = max(f[i],f[j] + 1);
}
if(f[i] > f[maxx])maxx = i;
}

cout << f[maxx] << endl;
int jmax = f[maxx];
for(int i=maxx-1;i>=1;i--)
{
if(f[i] == jmax - 1){jmax = f[i];b[jmax] = a[i];}
}
for(int i=1;i<=f[maxx]-1;i++)cout << b[i] << " ";cout << a[maxx];

}
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.