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

#include <cstdio>

int main(){
    int n,i,index;
    scanf("%d",&n);;
    int a[n];
    for(i = 0;i< n;i++) {
        scanf("%d",&a[i]);
    }
    int L[1000];
    for (i = 0; i < n; ++i) { //初始化，最长递增子序列长度为1
        L[i] = 1;

    }

    for (i = 1; i < n; ++i) {   //依次计算a【0】-a【i】的最长递增子序列
        int max = 1; // 初试时，递增子序列长度为1
        for (int j = i - 1; j >= 0; --j) {
            if ((a[j] < a[i]) && (max < L[j] + 1)) { //对于所有的a[j] < a[i],需要满足严格上升，且始终为最大长度
                max = L[j] + 1;
                L[i] = max;
            }
            }

        }
        for (index = 0,i=1; i < n; ++i) { // 求所有子序列的最大长度
            if (L[index] < L[i]){
                index = i;
            }
        }
        printf("%d",L[index]);

    return 0;
    }