C++语言编程 单调递增最长子序列

Question

7-1 单调递增最长子序列设计一个O(n2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。输入格式:输入有两行： 第一行：n，代表要输入的数列的个数 第二行：n个数，数字之间用空格格开输出格式:最长单调递增子序列的长度输入样例:在这里给出一组输入。例如：51 3 5 2 9输出样例:在这里给出相应的输出。例如：4

Answer 1

 #include <stdio.h>

#define MAX_N 1000

int dp[MAX_N], a[MAX_N];
int n;

void input()
{
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        scanf("%d", &a[i]);
}

int max_(int a, int b)
{
    return a > b ? a : b;
}

void slove()
{
    //注意要res保存结果
    int res = 0;
    for(int i = 0; i < n; ++i)
       {

        for(int j = 0; j < i; ++j)
            if(a[j] < a[i])
                dp[i] = max_(dp[i], dp[j] + 1);

        res = max_(dp[i], res);
       }
    printf("%d\n", res + 1);

}

int main()
{
    input();
    slove();
    return 0;
}