Cod sursa(job #3229058)

Utilizator Andreea1501013Andreea Andreea1501013 Data 13 mai 2024 16:31:00
Problema Subsir crescator maximal Scor 65
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>

using namespace std;
int v[100005],dp[100005],p[100005],save[100005];
int main()
{
  ifstream cin("scmax.in");
  ofstream cout("scmax.out");
  int n,maxi=0,t;
  cin>>n;
  for(int i=0;i<n;i++)
  {
      cin>>v[i];
      for(int j=i-1;j>=0;j--)
      {
          if(v[j]<v[i])
          if(dp[j]>dp[i])
          {
              dp[i]=dp[j];
              p[i]=j;
          }
      }
      dp[i]++;
      if(dp[i]>maxi)
      {
          maxi=dp[i];
          t=i;
      }
  }
  cout<<maxi<<endl;
  int k=0;
  while(t!=0)
  {
      save[k]=v[t];
      t=p[t];
      k++;
  }
  for(int l=k-1;l>=0;l--)
  {
      cout<<save[l]<<' ';
  }
    return 0;
}