Cod sursa(job #1752606)

Utilizator AhileGigel Frone Ahile Data 4 septembrie 2016 17:16:34
Problema Subsir crescator maximal Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include<bits/stdc++.h>
#define in f
#define out g
using namespace std;

ifstream f ("scmax.in");
ofstream g ("scmax.out");


int n;
int v[1000010];
int l[1000010];
int counter;

int dp() {

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j < i; j++) {
            if((v[j] < v[i])&&(l[i] < l[j] + 1)) {
                l[i] = 1 + l[j];
            }
        }
    }

}

int write() {
    int maxLen = l[1];
    int maxPos = 1;
    for(int i=2;i<=n;i++)
    {
        if(maxLen < l[i])
        {
            maxLen = l[i];
            maxPos = i;
        }

    }

    out << maxLen << endl;

    counter = maxLen;

  for(int i=1; i <= maxPos; i++)
  {
      if(v[i] < v[maxPos] && l[i] == maxLen + 1 - counter)
      {
         out << v[i] << " ";
          counter--;
      }

  }
  out << v[maxPos];

}

int main() {

    in >> n;
    for(int i = 1; i <= n; i++) {
        in >> v[i];
        l[i] = 1;
    }
    dp();
    write();

}