Cod sursa(job #1996620)

Utilizator mihailarminia1234Arminia Mihail mihailarminia1234 Data 2 iulie 2017 07:53:22
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <bits/stdc++.h>

using namespace std;

int n, v[100005], lis[100005], urm[100005], maxim, poz;

int main()
{
          freopen("scmax.in", "r", stdin);
          freopen("scmax.out", "w", stdout);
          scanf("%d", &n);
          for(int i = 1; i <= n; ++i) scanf("%d", &v[i]);
          lis[n] = 1; urm[n] = n + 1;
          for(int i = n - 1; i >= 1; --i)
          {
                    maxim =  0;
                    poz = n + 1;
                    for(int j = i + 1; j <= n; ++j)
                              if(v[i] < v[j] && lis[j] > maxim)
                              {
                                        maxim = lis[j];
                                        poz = j;
                              }
                    lis[i] = 1 + maxim;
                    urm[i] = poz;
          }
          maxim = lis[1]; poz = 1;
          for(int i = 2; i <= n; ++i)
                    if(lis[i] > maxim)
                    {
                              maxim = lis[i];
                              poz = i;
                    }
          printf("%d\n", maxim);
          while(poz != n + 1)
          {
                    printf("%d ", v[poz]);
                    poz = urm[poz];
          }
          return 0;
}