Mai intai trebuie sa te autentifici.
Cod sursa(job #525937)
| Utilizator | Data | 26 ianuarie 2011 19:20:27 | |
|---|---|---|---|
| Problema | Subsir crescator maximal | Scor | 0 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 1.06 kb |
#include <cstdio>
using namespace std;
void printSol(int* pred, int *a, int pos);
int main(void)
{
int N, i, j, maxLen, endPos;
int *a, *lengths, *pred;
freopen("scmax.in","r",stdin);
//freopen("scmax.out","w",stdout);
scanf("%d",&N);
a = new int[N];
lengths = new int[N];
pred = new int[N];
for (int i=0;i<N;i++)
{
scanf("%d",&a[i]);
}
lengths[0] = 1;
pred[0] = -1;
maxLen = 1;
endPos = 0;
for (i=1;i<N;i++)
{
lengths[i] = 1;
pred[i] = -1;
for (j=0;j<i;j++)
{
if(a[i] > a[j] && lengths[j] > lengths[i]-1)
{
lengths[i] = lengths[j] + 1;
pred[i] = j;
}
}
if (lengths[i] > maxLen)
{
maxLen = lengths[i];
endPos = i;
}
}
printf("%d\n",maxLen);
printSol(pred,a,endPos);
printf("\n");
delete[] a;
delete[] lengths;
delete[] pred;
return 0;
}
void printSol(int* pred, int *a, int pos)
{
if (pred[pos] != -1)
{
printSol(pred,a,pred[pos]);
}
printf("%d ",a[pos]);
}