Cod sursa(job #3177686)

Utilizator vlad231Gheorghica Istrate David vlad231 Data 29 noiembrie 2023 18:32:44
Problema Subsir crescator maximal Scor 35
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
vector<int> v;
int n,x,rez,lp;
int longestIncreasingSubsequence(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;

    vector<int> dp(n, 1);
int max_length=0;
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
                if(max_length<dp[i])
                {
                    max_length=dp[i];
                    lp=i;
                }
            }
        }
    }

  //  int max_length = *max_element(dp.begin(), dp.end());

    return max_length;
}
int main() {
fin>>n;
for(int i=1;i<=n;i++){
    fin>>x;
    v.push_back(x);
}
rez=longestIncreasingSubsequence(v);
fout<<rez<<'\n';
while(rez!=0){

    if(v[lp+1]>v[lp]){
        fout<<v[lp]<<" ";
      // fout<<v[lp]<<" "<<v[lp-1]<<" "<<rez<<'\n';
         rez--;
//fout<<rez<<" ";


}
lp--;
}
    return 0;
}