题解 | 最长上升子序列(一)

//  #牛客春招刷题训练营# https://www.nowcoder.com/discuss/726480854079250432
//  解题思路来自题解中C++的第一个，思路为动态规划
#include <iostream>
#include <vector>
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  int ans = 0;
  for(int i = 0; i < n; i++) cin >> a[i];
  vector<int> dp(n + 1, 1);//---------dp【i】表示以a【i】结尾的元素能构成的最长升序子序列
  for (int i = 0; i < n; i++){
    for (int j = 0; j < i; j++){//---------dp【i】 = max（dp【i】, dp[j]「 j满足,a[j]<a[i]&&j<i 」 + 1);
      if (a[j] < a[i])
        dp[i] = max(dp[j] + 1, dp[i]);
    }
  }
  for (int i = 0; i < n; i++)
    ans = max(ans, dp[i]);//--------ans取最值即可
  cout << ans;
}
// 64 位输出请用 printf("%lld")