Pagini recente » Cod sursa (job #1079780) | Cod sursa (job #2823630) | Cod sursa (job #154875) | Cod sursa (job #1526918) | Cod sursa (job #525938)
Cod sursa(job #525938)
#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]);
}