题意分析

给定一个长度为N的序列数组，输出最长的严格递增(如果$i < j$,则$a[i] < a[j])$的子序列长度。

解题思路

动态规划的经典问题之最长上升子序列问题

1. 状态集合
   $dp[i]$ 表示以第 $i$ 个数字结尾的最长的严格递增子序列的长度

2. 状态转移方程式
   假设 $L_0$~$L_k$ 表示一个严格递增序列，如果 $x>L_k$，则可将 $x$ 接到原递增序列后，构成一个新的严格递增序列。
   所以，如果 $j < i$ 且 $a[j] < a[i]$，则可有两种可能情况：

   • a. 将 $a[i]$ 接到以 $a[j]$ 为结尾的严格递增子序列后，即 $dp[i] = dp[j] + 1$
   • b. 不做任何处理，当前子序列表示不变，即 $dp[i] = dp[i]$
     综上，对于以第 $i$ 个元素为结尾的严格递增子序列长度来说，$dp[i] = \max\{a, b\}, j = 0 \sim i$

C++代码实现

cpp

#include <iostream>
using namespace std;
const int MAXN = 1005;
int value[MAXN];    //存放输入序列
int dp[MAXN];      //dp[i]表示以第i个元素(value[i])为结尾的最长递增子序列长度
int main() {
    int n;
    while(cin >> n) {
        for(int i = 0; i < n; i++) {
            cin >> value[i];
        }
        int res = -1;   //保存答案
        //状态转移
        for(int i = 0; i < n; i++) {
            dp[i] = 1;
            for(int j = 0; j < i; j++) {
                if(value[j] < value[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            res = max(res, dp[i]);      //更新最长长度大小
        }
        cout << res << endl;
    }
    return 0;
}