Cod sursa(job #978938)

Utilizator StefansebiStefan Sebastian Stefansebi Data 30 iulie 2013 15:22:39
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>

using namespace std;

int n, i, k, v[100000], lg[100000], p, maxi;
ifstream fin("scmax.in");
ofstream fout("scmax.out");

int main() {
    fin >> n;
    for (i = 0; i < n; i++)
        fin >> v[i];
    fin.close();
    //dinamica
    lg[n - 1] = 1;
    for (k = n - 2; k >= 0; k--) {
        maxi = 0;
        for (i = k + 1; i < n; i++)
            if (v[k] < v[i] and lg[i] > maxi)
                maxi = lg[i];
        lg[k] = 1 + maxi;
    }

   // for (i = 0; i < n; i++)
    //    fout << v[i] << ' ';
   // fout << '\n';
   // for (i = 0; i < n; i++)
   //     fout << lg[i] << ' ';
  //  fout << '\n';
    // o posibila varianta
    maxi = lg[0]; p = 0;
    // cautam primul maxim
    for (i = 1; i < n; i++)
        if (lg[i] > maxi) {
            maxi = lg[i]; p = i;
        }
    fout << maxi << '\n';
    fout  << v[p] << ' ';
    for (i = p + 1; i < n; i++)
        if (v[p] <= v[i] and lg[i] == maxi - 1) {
            fout << v[i] << ' '; maxi--;
        }
    fout.close();
    return 0;
}