Question

1.Sa se afiseze cea mai lunga secventa de numere strict crescatoare.De ex pt { 3, 10, 3, 11, 4, 5, 6, 7, 8, 12 }; se va afisa 3 4 5 6 7 8
2.Sa se afiseze cea mai lunga secventa care contine doar numere prime.
in c++ ,va roog e urgent.

Answer 1

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll const mod=1000000007;

ll const md=998244353;

ll mypowr(ll a,ll b) {ll res=1;a%=mod; assert(b>=0);

for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}

ll mypow(ll a,ll b) {ll res=1;assert(b>=0);

for(;b;b>>=1){if(b&1)res=res*a;a=a*a;}return res;}

ifstream in("elevi.in");

ofstream out("elevi.out");

#define mp make_pair

#define pb push_back

#define pf push_front

#define fi first

#define se second

vector<int> v[1005];

int f[1005];

ll dp[1005];

int p(ll x){

if(x<=1)return 0;

if(x<=3)return 1;

if(x%2==0||x%3==0)return 0;

for(ll i=5;i*i<=x;i+=6){

   if(x%i==0||x%(i+2)==0)return 0;

}

return 1;

}

int main()

{

   ios_base::sync_with_stdio(0);

   cout<<fixed<<setprecision(15);

   cin.tie(0);cout.tie(0);

   ll n;

   cin>>n;

   for(int i=1;i<=n;++i){

       cin>>f[i];

   }

   ll mx2=0,pos2=0;

   for(int i=1;i<=n;++i){

       v[i].pb(f[i]);

       int mx=0,pos=0;

       for(int j=i-1;j>=1;--j){

           if(f[i]>f[j]){

               if(dp[j]>mx){

                   mx=dp[j];

                   pos=j;

               }

           }

       }

       dp[i]=mx+1;

       if(pos>0){

           for(auto u:v[pos]){

               v[i].pb(u);

           }

       }

       if(dp[i]>mx2){

           mx2=dp[i];

           pos2=i;

       }

   }

   sort(v[pos2].begin(),v[pos2].end());

   for(auto u:v[pos2]){

       cout<<u<<" ";

   }

   cout<<'\n';

   for(int i=1;i<=n;++i){

       if(p(f[i])){

           cout<<f[i]<<" ";

       }

   }

   return 0;

}