最长递增子序列（DP 动态规划）

输入：
第一行： 数字个数
第二行 ：具体数据

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <windows.h>


#define MAX_SIZE 10000

int main() {
    int n;
    scanf("%d", &n);
    int v[MAX_SIZE] ={0};
    for (int i = 1; i <= n; i++) {
        scanf("%d", &v[i]);
    }
    int dp[MAX_SIZE];
    int path[MAX_SIZE];
    int vmax = 0;
    int vpos = 0;
// 1 7 3 5 9 4 8
// dp[1] = 1; vpos = 1; vmax =  1;
// dp[1]=1
// dp[2]=2
// dp[3]=2
// dp[4]=3
// dp[5]=4
// dp[6]=3
// dp[7]=4
    for (int i = 1; i <= n; i++) { //从数据的第一位开始
        int m = 0;    //默认当前的 子序 的个数
        for (int j = 1; j <= i; j++) { //第i位 以前
            if (v[j] < v[i]) {       //如果第 j 位 比 第 i 位 小 说明有 子序列
                if (dp[j] > m) {    //如果 当前位的 子序 个数 比m 大，
                    path[i] = j;    //则 将 j的位置放在路径数组中
                }
                m  = max(m, dp[j]); //m 为当前 子序个数 最大值
            }
        }
        dp[i] = m + 1;  
        if (dp[i] > vmax) {
           vpos = i; //记录最大的 值得位置
        }
        vmax = max(dp[i], vmax);
        printf("dp[%d]=%d\n", i, dp[i]);
    }
    printf("%d\n", vmax);
    // 路径回溯
    while (vpos > 0) {
        printf("%d", vpos);
        vpos = path[vpos];
    }
    system("pause");
    return 0;
}