Pagini recente » Cod sursa (job #2953646) | Cod sursa (job #583047) | Cod sursa (job #2382270) | Cod sursa (job #2725503) | Cod sursa (job #1730716)
#include<stdio.h>
int v[100001], n, i, j, lmax[100001], pred[100001], lungimeMaxima, raspunsLungime = -1, raspunsPozitie, vafis[100001], k = 0;
int main()
{
FILE *inputFile = fopen("scmax.in", "r"), *outputFile = fopen("scmax.out", "w");
fscanf(inputFile, "%d", &n);
for(i = 1; i <= n; i++)
fscanf(inputFile, "%d", v+i);
lmax[1] = 1; pred[1] = -1;
for(i = 2; i <= n; i++)
{
lungimeMaxima = -1;
for(j = 1; j < i; j++)
if(lmax[j] > lungimeMaxima && v[j] < v[i])
{
lungimeMaxima = lmax[j];
pred[i] = j;
lmax[i] = lungimeMaxima + 1;
if(lmax[i] > raspunsLungime)
{
raspunsLungime = lmax[i];
raspunsPozitie = i;
}
}
if(lungimeMaxima == -1)
{
lmax[i] = 1;
pred[i] = -1;
}
}
fprintf(outputFile, "%d\n", raspunsLungime);
i = raspunsPozitie;
while(pred[i] != -1)
{
vafis[++k] = v[i];
i = pred[i];
}
vafis[++k] = v[i];
for(i = k; i >= 1; i--)
fprintf(outputFile, "%d ", vafis[i]);
return 0;
}