Pagini recente » Cod sursa (job #2550871) | Cod sursa (job #1514078) | Cod sursa (job #2765091) | Cod sursa (job #1618151) | Cod sursa (job #3182568)
#include <iostream>
#include <algorithm>
using namespace std;
int dp[100005];
int v [100005];
int succ[100005];
/*
Subproblema: cel mai lung subsir
crescator maximal care incepe cu pozitia i.
*/
int main()
{
cin.tie(0); cin.sync_with_stdio(false);
cout.tie(0); cout.sync_with_stdio(false);
freopen("scmax.in", "r", stdin);
freopen("scmax.out", "w", stdout);
int n, elem;
cin>>n;
for (int i=1; i<=n; i++) cin>>v[i];
for (int i=n; i>=1; i--) {
dp[i]=0;
for (int j=i+1; j<=n; j++) {
if (v[j]>v[i]&&dp[j]>dp[i]) {
dp[i]=dp[j];
succ[i]=j;
}
}
dp[i]++;
}
int maxi=-1, poz=0;
for (int i=1; i<=n; i++) {
if (dp[i]>maxi) {
maxi=dp[i];
poz=i;
}
}
cout<<maxi<<'\n';
while (succ[poz]!=0) {
cout<<v[poz]<<' ';
poz=succ[poz];
}
cout<<v[poz]<<' ';
return 0;
}