Pagini recente » Cod sursa (job #2172821) | Cod sursa (job #1349265) | Cod sursa (job #1342926) | Cod sursa (job #836980) | Cod sursa (job #1752606)
#include<bits/stdc++.h>
#define in f
#define out g
using namespace std;
ifstream f ("scmax.in");
ofstream g ("scmax.out");
int n;
int v[1000010];
int l[1000010];
int counter;
int dp() {
for(int i = 1; i <= n; i++) {
for(int j = 1; j < i; j++) {
if((v[j] < v[i])&&(l[i] < l[j] + 1)) {
l[i] = 1 + l[j];
}
}
}
}
int write() {
int maxLen = l[1];
int maxPos = 1;
for(int i=2;i<=n;i++)
{
if(maxLen < l[i])
{
maxLen = l[i];
maxPos = i;
}
}
out << maxLen << endl;
counter = maxLen;
for(int i=1; i <= maxPos; i++)
{
if(v[i] < v[maxPos] && l[i] == maxLen + 1 - counter)
{
out << v[i] << " ";
counter--;
}
}
out << v[maxPos];
}
int main() {
in >> n;
for(int i = 1; i <= n; i++) {
in >> v[i];
l[i] = 1;
}
dp();
write();
}