Cod sursa(job #373794)

Utilizator juniorOvidiu Rosca junior Data 15 decembrie 2009 06:14:36
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>

using namespace std;

ifstream fi("scmax1.in");
ofstream fo("scmax.out");
int l[100001], a[100001], n, lmax, imax;

void citeste () {
  int i;
  
  fi >> n;
  for (i = 1; i <= n; i++)
    fi >> a[i];  
}

void dinamic() {
  int ml, i, j;
  // ml - maximul lungimilor subsirurilor crescatoare care incep dupa pozitia "i" cu un element >= a[i]
  
  l[n] = 1;
  for (i = n-1; i >= 1; i--) {
    ml = 0;  
    for (j = i+1; j <= n; j++)
      if (a[j] > a[i] and l[j] > ml)
        ml = l[j];
    l[i] = ml+1;
  }
}

void maxim () {
  int i;
  
  lmax = l[1]; imax = 1;
  for (i = 1; i <= n; i++)
    if (l[i] > lmax) {
      lmax = l[i]; imax = i;
    }
}  

void scrie() {
  int i;
  
  fo << lmax << endl;
  for (i = imax; i <= n; i++)
    if ((a[i] >= a[imax]) and (lmax == l[i])) {
      fo << a[i] << ' ';
      lmax--;
    }
}

int main() {
  citeste();
  dinamic();
  maxim();
  scrie();
  return 0;
}