Pagini recente » Cod sursa (job #642706) | Cod sursa (job #662876) | Cod sursa (job #2426397) | Cod sursa (job #1783147) | Cod sursa (job #705314)
Cod sursa(job #705314)
#include<fstream>
#define DIM 100001
using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
int Best[DIM], Pre[DIM];
int N, maxim, poz;
long long V[DIM];
void rebuild(int pozitie)
{
if( Pre[pozitie] == 0 )
{
out << V[pozitie] << " ";
return;
}
else {
rebuild( Pre[pozitie] );
out << V[pozitie] << " ";
}
}
int main()
{
int i, j;
in >> N;
for(i = 1; i <= N; i++)
in >> V[i];
Best[1] = 1; // lungimea unui subsir crescator care se termina in 1
for(i = 2; i <= N; i++)
{
maxim = 0;
for(j = 1; j < i; j++)
if( V[j] < V[i] )
if( Best[j] > maxim )
{
maxim = Best[j];
poz = j;
}
Best[i] = 1 + maxim;
Pre[i] = poz;
}
maxim = 0;
for(i = 1; i <= N; i++)
if( Best[i] > maxim )
maxim = Best[i], poz = i;
out << maxim << '\n';
rebuild(poz);
}