acwing 895 最长上升子序列1

#include<iostream>
#include<cstring>
#include<algorithm>
 
using namespace std ;
typedef long long LL ; 
const LL N = 1010 ;
LL n ;
LL a[N] ; 
LL f[N][N] ;//表示前i个数以j结尾的最长上升子序列长度
 
int main(){
  int n ; cin >> n ;
  for(int i = 1 ; i <= n ; i ++) cin >>a[i] ;
  f[1][1] = 1;
  for(int i = 1 ; i <= n ; i ++) f[i][i] = 1 ;// 每一个数的长度初始化为1
  for(int i = 2 ; i <= n ; i ++){
    for(int j = 1 ; j < i ; j ++){
      f[i][j] = f[i-1][j] ;// 继承前i-1个数的以j结尾的最长上升子序列数
      if(a[i] > a[j]) f[i][i] = max(f[i][i] , f[i-1][j] + 1) ;
                //我们只需要更新f[i][i]的长度因为只有i是新加入的
                //对于每一个符合if条件的 我们都取 当前的 和 加1的 的最大值
    }
  }
  LL ans = 0 ;
  for(int i = 1 ; i <= n ; i ++ ) ans = max(ans , f[n][i]) ;
    //前n个数 找数组中的最大值即为最终答案
  cout << ans << endl ;
  return 0 ;
}

 
//一维数组答案  麻痹我自己写的麻烦了  才发现
#include<iostream>
#include<algorithm>
#include<cstring>
 
using namespace std ;
const int N = 1010 ;
int  a[N] ;
int len[N] ;
int main(){
  int n ; cin >> n ;
  for(int i = 1 ; i <= n ; i ++) cin >> a[i] ;
  
  for(int i = 1 ; i <= n ; i ++){
    len[i] ++ ;
    for(int j = 1 ; j < i ; j ++){
      if(a[j] < a[i]){
        len[i] = max(len[i] , len[j] + 1);
      } 
    }
  }
  int ans = 0 ;
  for(int i = 1 ; i<=n ;i ++) ans = max(ans, len[i]) ;
  cout << ans << endl ;
  return 0; 
}