問題描述
給定一個長度為N NN的數列，求數值嚴格單調遞增的子序列的長度最長是多少。

輸入格式：
第一行包含整數N NN。

第二行包含N NN個整數，表示完整序列。

輸出格式：
輸出一個整數，表示最大長度。

數據范圍
1 ≤ N ≤ 1000 ， 1≤N≤1000，1≤N≤1000，
? 109 ≤ 數 列 中 的 數 ≤ 109 ?109≤數列中的數≤109?109≤數列中的數≤109

輸入樣例：
7
3 1 2 1 8 5 6
1
2
輸出樣例：
4
1
思路
1、可以使用dp的方式進行求解。
2、分為狀態表示和狀態計算，狀態表示所表示的集合是所有以第i個數結尾的上升子序列。
3、極端情況：f[i] = 1恒成立 因為在當只有一個以第i個數結尾的時候就是1；
4、當滿足f[j] < f[i] 的時候 即 滿足上升的性質 后面一個數比前面一個數字大，則可以使用狀態轉移方程式 f[i] = max(f[i], f[j] + 1) 理解為所有以j結尾的所有的上升子序列長度的最大值為 fj + 1 即可得到最大值

#include<iostream>
using namespace std;
const int N = 1010;
int a[N], f[N]; //f[N]表示從1-n,每個下標的最長序列
int n, ans;
int main()
{cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];for (int i = 1; i <= n; i++){f[i] = 1;  //首先當前下標的最長上升序列至少為1(它本身)for (int j = 1; j < i; j++){if (a[j] < a[i])  //下標j從 1~i-1 開始，如果a[j]<a[i],那么就有兩個選擇{//1-j的最長上升序列為f[j],此時a[i]又大于a[j],所以f[i]至少有f[j]+1個最長上升序列，然后取最大值f[i] = max(f[i], f[j] + 1);}}}for (int i = 1; i <= n; i++)ans = max(ans, f[i]);cout << ans << endl;return 0;
}

算法小白的學習筆記