Cod sursa(job #1873966)

Utilizator PetrescuAlexandru Petrescu Petrescu Data 9 februarie 2017 16:02:00
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <stdio.h>
#include <iostream>
#define MAX 100000

using namespace std;
int v[MAX], lmax[MAX], scmax[MAX];
int main()
{
  FILE *fin, *fout;
  int n, i, max, j;

  fin = fopen("scmax.in", "r");
  fout = fopen("scmax.out", "w");
  fscanf(fin, "%d", &n);
  for(i = 0; i < n; i++)fscanf(fin, "%d", &v[i]);
  lmax[0] = 1;
  for(i = 1; i < n; i++)
  {
    max = 0;
    for(j = i - 1; j >= 0; j--)
      if(v[j] < v[i] && max < lmax[j])max = lmax[j];
    lmax[i] = max + 1;
  }
  max = 0;
  for(i = 0; i < n; i++)if(max < lmax[i])max = lmax[i];
  fprintf(fout, "%d\n", max);
  j = 0;
  for(i = n - 1; i >= 0; i--)
  {
    if(lmax[i] == max)
    {
      scmax[j] = v[i];
      j++;
      max--;
    }
  }
  for(j = j - 1; j >= 0; j--)fprintf(fout, "%d ", scmax[j]);
  fclose( fin );
  fclose( fout );
  return 0;
}