Cod sursa(job #2972424)

Utilizator dumitrache12Dumitrache Iulian dumitrache12 Data 29 ianuarie 2023 14:20:32
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include<bits/stdc++.h>
using namespace std;

ifstream in ("scmax.in");
ofstream out("scmax.out");
// auto& in = cin;
// auto& out = cout;

int const N = 100005;
int n, v[N], best[N], nxt[N];
int res, start;

void read()
{
	in>>n;
	for(int i=1; i<=n; i++)
	{
		in>>v[i];
		best[i] = 1;
	}
}

void dinamic(int n)
{
  res=1;  start=n;
  for(int i=n-1;i>=1;--i)
    for(int j=i+1;j<=n;++j)
        if(v[i]<v[j] && best[i]<best[j]+1)
        {
          best[i]=best[j]+1;
          nxt[i]=j;
          if(best[i]>res) res=best[i],start=i;
        }  
}

void reconstruct()
{
	out<<res<<'\n';
	for(int p=start; p; p=nxt[p])
		out<<v[p]<<' ';
	out<<endl;
}

int main(){
	read();
	dinamic(n);
	reconstruct();
	return 0;
}