Cod sursa(job #525938)

Utilizator icepowdahTudor Didilescu icepowdah Data 26 ianuarie 2011 19:21:15
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 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]);
}