# include < iostream >
# include < cstring >
using namespace std ;
const int MAX_SIZE = 1000 ;
int sequence [MAX_SIZE];
int dp [MAX_SIZE];
int n;
int longest_increasing_subsequence_dp ( int idx ) {
if ( dp [ idx ] != -1 ) {
return dp [ idx ];
}
int max_len = 1 ;
for ( int i = idx + 1 ; i < n; i++) {
if ( sequence [i] > sequence [ idx ]) {
max_len = max ( max_len , 1 + longest_increasing_subsequence_dp (i));
}
}
dp [ idx ] = max_len ;
return dp [ idx ];
}
int main () {
cin >> n;
for ( int i = 0 ; i < n; i++) {
cin >> sequence [i];
}
memset ( dp , -1 , sizeof ( dp ));
int max_len_dp = 0 ;
for ( int i = 0 ; i < n; i++) {
max_len_dp = max ( max_len_dp , longest_increasing_subsequence_dp (i));
}
cout << "Lungimea maxima (DP): " << max_len_dp << endl ;
return 0 ;
}
# include < iostream >
# include < climits >
using namespace std ;
const int MAX_SIZE = 1000 ;
int sequence [MAX_SIZE];
int n;
int longest_increasing_subsequence_greedy ( int idx ) {
int current = sequence [ idx ];
int len = 1 ;
for ( int i = idx + 1 ; i < n; i++) {
if ( sequence [i] > current ) {
len ++;
current = sequence [i];
}
}
return len ;
}
int main () {
cin >> n;
for ( int i = 0 ; i < n; i++) {
cin >> sequence [i];
}
int max_len_greedy = 0 ;
for ( int i = 0 ; i < n; i++) {
max_len_greedy = max ( max_len_greedy , longest_increasing_subsequence_greedy (i));
}
cout << "Lungimea maxima ( Greedy ): " << max_len_greedy << endl ;
return 0 ;
}