LIS (最长递增子序列) 朴素版

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define mod 998244353
#define endl '\n'
using namespace std;
typedef long long LL;
typedef pair<int, int>PII;
const int N = 1010;
int n;
int dp[N], a[N];
// dp[i] 以第 i 个数结尾的上升子序列的最大长度
void solve() {
  cin >> n;
  for (int i = 1; i <= n; ++i)scanf("%d",a + i);
  for (int i = 1; i <= n; ++i) {
    dp[i] = 1;
    for (int j = 1; j <= i; ++j) {
      if (a[j] < a[i])
        dp[i] = max(dp[i], dp[j] + 1);
    }
  }
  int res = -INF;
  for (int i = 1; i <= n; ++i) {
    res = max(res, dp[i]);
  }
  cout << res << endl;
}
int main() {
  //int t; cin >> t;
  //while (t--)
    solve();
  return 0;
}