Cod sursa(job #2866965)

Utilizator C_R_I_S_T_I_2_3Cristi Gavrila C_R_I_S_T_I_2_3 Data 10 martie 2022 09:17:58
Problema Subsir crescator maximal Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n, sol = 0, u;
int v[100005], dp[100005];
stack<int> s;
int main()
{
    fin >> n;
    for(int i = 1; i <= n; i ++)
        fin >> v[i];
    dp[1] = 1;
    for(int i = 2; i <= n; i ++)
    {
        int maxim = 0;
        for(int j = 1; j < i; j ++)
            if(v[j] < v[i])
                maxim = max(maxim, dp[j]);
        dp[i] = maxim + 1;
        sol = max(sol, dp[i]);
    }
    fout << sol << "\n";
    for (int i = n; i >= 1; i --)
    {
        if(dp[i] == sol && (u > v[i] || u == 0))
        {
            s.push(i);
            u = v[i];
            sol --;
        }
    }
    while(!s.empty())
    {
        fout << s.top() << " ";
        s.pop();
    }
    return 0;
}