Cod sursa(job #1677014)

Utilizator MasurceacMasurceac Serghei Masurceac Data 6 aprilie 2016 12:05:40
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <fstream>
using namespace std;
int sir[100000], best[100000], rez[100000];

int poz_pred_max(int poz)
{
    int rs = poz; bool gasit = 0;
    while ((rs>-1) &&(gasit==0))
    {
        --rs;
        if (sir[rs]<sir[poz])
        {
            gasit=1;
        }
    }
    if (gasit==0) return -1;
    else return rs;
}

int main()
{
    ifstream f("scmax.in");
    int n; f>>n;
    int i;
    for (int i=0; i<n; i++)
    {
        f>>sir[i];
        best[i] = 0;
    }
    f.close();
    best[0] = 1;
    for (i=1; i<n; i++)
    {
        if (poz_pred_max(i)!=-1)
        {
            best[i] = 1 + best[poz_pred_max(i)];
        }
        else best[i] = 1;
    }
    int pmax=best[0], maxpoz=1;
    for (i=0; i<n; i++)
        if (best[i]>pmax)
    {
        pmax=best[i];
        maxpoz=i;
    }
    int rs=pmax;
    rez[pmax] = sir[maxpoz];
    for (i=1; i<rs; i++)
    {
        --pmax;
        maxpoz=poz_pred_max(maxpoz);
        rez[pmax] = sir[maxpoz];
    }
    ofstream f2("scmax.out");
    f2<<rs<<endl;
    for (int i=1; i<=rs; i++)
        f2<<rez[i]<< " ";

    return 0;
}