Cod sursa(job #2280413)

Utilizator ZappaManIosif Adrian-Mihai ZappaMan Data 10 noiembrie 2018 16:03:47
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <iostream>
#include <fstream>

typedef long long T;

const int NMAX = 100005;

int N;

T arr[NMAX];

T best[NMAX];
T pre[NMAX];

/*
 *
 * am asa 
 * best_i = 1 + max(best_j)
 * pre_i -> pozitie valorii care preceda elementul i din subsir 
 *
 */



int main() {
   freopen("scmax.in", "r", stdin);
   freopen("scmax.out", "w", stdout);

   scanf("%d", &N);

   for (int i = 0; i < N; ++i) {
      scanf("%lld", &arr[i]);
   }

   T max = -1;
   int p = -1;

   for (int i = 0; i <= N; ++i ) {
      best[i] = 1;
      pre[i] = -1;
   }

   best[N-1] = 1;
   pre[N-1] = -1;   

   for (int i = N-1; i >= 0; --i) {
      best[i] = 1;
      pre[i] = -1;
      for (int j = i+1; j < N; ++j) {
         if (arr[i] < arr[j] && best[i] < best[j] + 1) {
            best[i] = best[j] + 1;
            pre[i] = j;
            if (max < best[i]) {
               max = best[i];
               p = i;
            }
         }
      }
   }

   printf("%lld\n", max);
   while (p != -1) {
      printf("%lld ", arr[p]);
      p = pre[p];
   }

   return 0;
}