Pagini recente » Cod sursa (job #876528) | Cod sursa (job #914010) | Cod sursa (job #693561) | Cod sursa (job #2354274) | Cod sursa (job #3182580)
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
#define fastIO ios_base::sync_with_stdio(NULL);cin.tie(NULL)
#define testCases int tc;cin>>tc;while(tc--)
#define ll long long
#define ld long double
#define sza(x) ((int)x.size())
#define all(a) (a).begin(),(a).end()
#define PI 3.1415926535897932384626433832795l
const int NMAX = 1e5 + 5;
template<typename T> inline T gcd(T a, T b) {return (b?__gcd(a, b):a);}
template<typename T> inline T lcm(T a, T b) {return (a*(b/gcd(a, b)));}
static inline void solve();
void print ( int x, int* last, int* a )
{
if ( a [ x ] == 0 ) return;
cout << a [ x ] << ' ';
print ( last [ x ], last, a );
}
int main ( int argc, char** argv )
{
( void )! freopen ( "scmax.in" , "r" , stdin );
( void )! freopen ( "scmax.out" , "w" , stdout );
fastIO;
solve();
return 0;
}
static inline void solve()
{
// exemplu de dp
// int dp [ 3 ];
// dp [ 0 ] = 1, dp [ 1 ] = 2;
// int n; cin >> n;
// int i = 1;
// while ( i < n )
// {
// dp [ ( i + 1 ) % 3 ] = dp [ i % 3 ] + dp [ ( i - 1 ) % 3 ];
// i ++;
// }
// cout << dp [ ( i - 1 ) % 3 ];
//
int n; cin >> n;
int a [ NMAX ], best [ NMAX ], last [ NMAX ];
best [ 1 ] = 1;
for ( int i = 1; i <= n; ++ i )
cin >> a [ i ];
for ( int i = n; i >= 1; -- i )
{
int min = 0;
for ( int j = i + 1; j <= n; ++ j )
{
if ( a [ i ] < a [ j ] && best [ j ] > min ) min = best [ j ], last [ i ] = j;
}
best [ i ] = 1 + min;
}
int max = 0, prev = 0;
for ( int i = 1; i <= n; ++ i )
{
if ( best [ i ] > max ) max = best [ i ], prev = i;
}
cout << max << '\n';
print ( prev, last, a );
}