Cod sursa(job #2213432)

Utilizator Alex03Runcan Alexandru Alex03 Data 16 iunie 2018 14:07:22
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int length,sequence[100001],temporaryArray[100001],Solution[100001],Solution2[100001];

void LIS ()
{
    int i,j;
    for (i = 1; i <= length ; i++)
    {
        temporaryArray[i] = 1;
        Solution[i] = i;
    }

    for (i = 2; i <= length ; i++)
        for (j = 1; j <= i ; j++)
        {
            if (sequence[i] >sequence [j] && temporaryArray[j] + 1 > temporaryArray[i])
            {
                temporaryArray[i] = temporaryArray [j] + 1;
                Solution[i] = j;
            }
        }

    int maxIndex = 0;
    for (i = 1; i <= length; i++)
        if (temporaryArray[i] > temporaryArray[maxIndex]) maxIndex = i;

    int t = maxIndex;
    fout << temporaryArray[maxIndex] <<endl;
    int newT = maxIndex;
    i = 1;
    do
    {
        t = newT;
        Solution2[i] = sequence[t];
        newT = Solution [t];
        i++;
    }
    while (t != newT);
    for (i-- ; i>=1; i--)
        fout << Solution2[i]<<' ';
}

int main ()
{
    fin >> length;
    for (int i = 1; i <= length; i++)
        fin >> sequence[i];
    LIS();
    return 0;
}