Pagini recente » Cod sursa (job #2524911) | Cod sursa (job #566457) | Cod sursa (job #2818620) | Cod sursa (job #1541322) | Cod sursa (job #357463)
Cod sursa(job #357463)
//Probleme: subsiruri, decrease.
#include <cstdio>
#define N 100001
int lung_max=0,poz_lung_max;
int v[N];
int lung[N];//lung[i] = lungimea celui mai mare subsir crescator care are ultimul element v[i].
int pred[N];//pred[i] = pozitia elementului precedent elem de pe poz i in subsirul in care l-am adaugat.
void adaugare(int poz)
{
int max_lung_pred=0; //Lungimea celui mai mare subsir anterior la care se poate lipi numarul.
int poz_i; //Pozitia unde se gaseste ultimul element al subsirului respeciv.
bool gasit=false;
for (int i = 1; i <= poz; ++i)
if ((v[i] < v [poz])&&(lung[i]>max_lung_pred))
{
gasit = true;
poz_i = i;
max_lung_pred = lung[i];
}
if (gasit)
{
lung[poz] = lung[poz_i]+1;
pred[poz] = poz_i;
}
else
{
lung[poz] = 1;
pred[poz] = 0;
}
if (lung[poz]>lung_max)
{
lung_max = lung[poz];
poz_lung_max = poz;
}
}
void printv(int poz)
{
if (pred[poz]!=0)
printv(pred[poz]);
printf("%d ",v[poz]);
}
void afisare()
{
printf("%d\n",lung[poz_lung_max]);
printv(poz_lung_max);
}
int main()
{
int n;
freopen("scmax.in","r",stdin);
freopen("scmax.out","w",stdout);
scanf("%d",&n);
for (int i = 1; i <= n; ++i)
{
scanf("%d",&v[i]);
adaugare(i);
}
afisare();
return 0;
}