Pagini recente » Cod sursa (job #3293326) | Cod sursa (job #3293286)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n,v[100001],dp[100001],poz[100001],maxi,pozitie;
vector<int> a;
int main()
{
fin>>n;
for(int i=1;i<=n;i++){
fin>>v[i];
dp[i]=1;
}
///dp[i]-subsirul maxim crescator pana la i
for(int i=1;i<=n;i++){
for(int j=i-1;j>=1;j--){
if(v[i]>v[j]){
if(dp[j]+1>dp[i]){
dp[i]=dp[j]+1;
poz[i]=j;
}
}
}
}
for(int i=1;i<=n;i++){
if(maxi<dp[i]){
maxi=dp[i];
pozitie=i;
}
}
fout<<maxi<<'\n';
while(maxi){
a.push_back(v[pozitie]);
pozitie=poz[pozitie];
maxi--;
}
reverse(a.begin(),a.end());
for(auto u:a){
fout<<u<<" ";
}
return 0;
}