Cod sursa(job #2269884)

Utilizator SahMatCodrea Andrei SahMat Data 26 octombrie 2018 18:28:18
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>

using namespace std;

ifstream fi("scmax.in");
ofstream fo("scmax.out");

int n;
int a[100001];
int dp[100001],ml;
int poz;
int main()
{
    fi>>n;
    for(int i=1; i<=n; i++)
        fi>>a[i];

    dp[n]=1;
    for(int i=n-1; i>=1; i--)
    {
        ml = 0;
        for(int j=i+1; j<=n; j++)
            if(a[j]>a[i] and dp[j] > ml)
                {
                    ml=dp[j];
                }
        dp[i]=ml+1;
    }
    int ma=0;
    for(int i=1;i<=n;i++)
        if(dp[i]>ma)
    {
        ma=dp[i];
        poz=i;
    }

    int k=ma;
    fo<<k << '\n';
    fo<<a[poz]<<' ';
    k--;
    while(k)
    {
        for(int i=poz;i<=n;i++)
        {
            if(dp[i]==dp[poz]-1 and a[poz]<a[i])
            {
                k--;

                poz=i;

                fo<<a[i]<<" ";
            }
        }
    }
    return 0;
}

//maximul lungimilor subsirurilor crescatoare care incep dupa pozitia "i" cu un element >= a[i]