Cod sursa(job #1719710)

Utilizator radu.bRadu Brumariu radu.b Data 20 iunie 2016 03:33:46
Problema Subsir crescator maximal Scor 35
Compilator c Status done
Runda Arhiva educationala Marime 0.85 kb
#include<stdio.h>

#define NMAX 100000

int a[NMAX], best[NMAX], pos[NMAX];

int compute(int n, int *max) {
  int i, j, p;
  best[n] = 1;
  pos[n] = -1;
  *max = 1;
  p = n;
  for(i = n-1; i >= 0; i--) {
    best[i] = 1;
    pos[i] = -1;
    for(j = i; j <= n; j++ ) {
      if(a[i] < a[j] && best[i] < best[j] + 1) {
        best[i] = best[j]+1;
        pos[i] = j;
        p = i;
        if(*max < best[i]) *max = best[i];
      }
    }
  }
  return p;
}

void display(int p, int max) {
  int i = p;
  printf("%d\n", max);
  while(pos[i] != -1) {
    printf("%d ", a[pos[i]]);
    i = pos[i];
  }
  printf("\n");
}

int  main() {
  freopen("scmax.in", "r", stdin);
  freopen("scmax.out", "w", stdout);
  int N, max, end_pos;
  scanf("%d", &N);
  for(int i = 0; i < N; i++) {
    scanf("%d", &a[i]);
  }

  end_pos = compute(N, &max);
  display(end_pos, max);
  return 0;
}