Cod sursa(job #2042313)

Utilizator skeniaTirla Ovidiu skenia Data 18 octombrie 2017 13:21:56
Problema Subsir crescator maximal Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ("scmax.in");
ofstream fout ("scmax.out");

int length;
pair<int,int>con[100005];
int lengthCon = 1;
int finalMax = 0, finalMaxPoz = 0;
int getAssosciat(int number){
    int pozMax = 0;
    for(int iter = lengthCon; iter > 0; --iter){
        if(con[iter].first < number){
            pozMax = max(pozMax, con[iter].second);
            if(pozMax == finalMax){
                finalMax = pozMax + 1;
                finalMaxPoz = lengthCon;
                return pozMax + 1;
            }
        }
    }
    if(pozMax > finalMax){
        finalMax = pozMax + 1;
        finalMaxPoz = lengthCon;
    }
    return pozMax + 1;
}
void reversePrint(int poz){
    if(con[poz].second != 0){
        reversePrint(con[poz].second);
        fout<<con[poz].first<<' ';
    }
}
int main()
{
    fin>>length;
    int temp;
    fin>>temp;
    con[lengthCon].first = temp;
    con[lengthCon].second = 0;
    lengthCon++;
    for(int iter = 2; iter <= length; ++iter){
        fin>>temp;
        con[lengthCon].first = temp;
        con[lengthCon].second = getAssosciat(temp);
        lengthCon++;
    }
    fout<<con[finalMaxPoz].second<<'\n';
    reversePrint(finalMaxPoz);
    fin.close();
    fout.close();
    return 0;
}