求数组中最长递增子序列—动态规划入门（编程之美）

#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int maxm = 10000;int a[maxm];int value[maxm]; //记录当前最优解int n;//时间复杂度O（n*n)int work(){    for(int i = 1; i <= n; i++) {        value[i] = 1;        for(int j = 1; j <= i; j++) {            if(a[i] > a[j] && value[j] + 1 > value[i]) {                value[i] = value[j] + 1;            }        }    }    int maxn = 1;    for(int i = 1; i <= n; i++) {        if(maxn < value[i]) {            maxn = value[i];        }    }    return maxn;}int main(){    scanf("%d", &n);    for(int i = 1; i <= n; i++) {        scanf("%d", &a[i]);    }    int res = work();    cout << res << endl;    return 0;}//参考编程之美P195