Cod sursa(job #3182572)

Utilizator christalknightChristian Micea christalknight Data 9 decembrie 2023 10:32:45
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include <fstream>
#include <stack>

using namespace std;

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

const int nmax = 100003;

stack <int> st;

int main(){
    int i = 1, j, n, dp[2][nmax], predecesori[nmax], maxim = -1, maxPoz; 

    fin>>n;
    
    fin>>dp[0][1];
    dp[1][1] = 1;
    predecesori[1] = 0;

    for(i = 2; i <= n; i++){
        fin>>dp[0][i];
        dp[1][i] = 0;

        for(j = i - 1; j >= 1; j--)
            if(dp[0][i] > dp[0][j]){
                //dp[1][i] = max(dp[1][i], dp[1][j]);
                if(dp[1][i] < dp[1][j]){
                    predecesori[i] = j;
                    dp[1][i] = dp[1][j];
                    }
                //cout<<"pt i = "<<i<<", j = "<<j<<", dp[0][j] = "<<dp[0][j]<<"\n";
                }
        
        dp[1][i]++;
        if(dp[1][i] > maxim){
            maxim = dp[1][i];
            maxPoz = i;
            }
        }

    /*for(i = 1; i <= n; i++)
        fout<<dp[0][i]<<" "<<dp[1][i]<<"\n";
    for(i = 1; i <= n; i++)
        fout<<predecesori[i]<<"\n";*/

    fout<<maxim<<"\n";
    st.push(dp[0][maxPoz]);
    while(predecesori[maxPoz]){
        st.push(dp[0][predecesori[maxPoz]]);
        maxPoz = predecesori[maxPoz];
        }

    while(!st.empty()){
        fout<<st.top()<<" ";
        st.pop();
        }
    }