编程题-求最长递增子序列的数量

最长递增子序列的数量

• 出处：今日头条内推一面编程题
• 题目：有一个无序数组，现需要你找到最长的递增的子序列的个数。

eg1： 1 2 4 3 5
最长的递增子序列是 1 2 4 5 和 1 2 3 5,所以应输出2。
eg2:1 1 1 1 1
输出5，即是5个长度为1 的 1

思路

我们从数组下标为0开始，0下标时，包含当前位置的最大长度只能是1，并且次数是1，下标为1时，包含1下标的最长递增序列需要和0位去比较，a[1]> a[0]那么自然会将长度更新为2，出现的次数赋初值1，若小于或者的等于，那么包含1下标的字串就是a[1]本身，最长为1，出现次数为1，然后按照这种方式去判断之后的下标。

这个，很明显是要用到动态规划的思路，而且这个不是简单的DP，但前位置的结果，不单单由他前一位去决定，而是由其前面所有来决定，那么整理下思路：

用 a[] = 1 2 4 3 5 来举例。
现在需要一个辅助数组a_t[2][len(a)]。这个数组的第一行，存的是以该下标位置的数字作为结束，最长的递增字串的长度。为何一定要用该位置做结尾，因为我们不清楚，或许当前看来选择这里个下标使得字串长度变小，但不确定以后这个长度是否会超过不选择该下标。数组第二行，存的是该长度的字串的个数。
那么最终a_t = {
1,2,3,3,4
1,1,1,1,2
}
即可得知最长字串是4个长度，出现了2次。

#include<stdio.h>
#include<string.h>
int main(void){
    int n;
    scanf("%d",&n);
    int a[n];
    int i,j;
    for(i = 0;i<n;i++){
        scanf("%d",&a[i]);
    }
    int a_t[2][n];
    memset(a_t,0,2*n*4);

    a_t[0][0] = 1;
    a_t[1][0] = 1;
    for(i = 1;i<n;i++){
        int max = 1;
        int times = 1;
        for(j = 0;j<i;j++){
            int m = 1;
            //m代表当前的长度，最少是1
            if(a[i] > a[j]){
                m = a_t[0][j] + 1;
                //如果当前的这一位比前面的某一位大，则说明会使长度增加
            }
            else if(a[i] == a[j]){
                //相等则不改变最大长度
                m  = a_t[0][j];
            }
            //更新最大长度以及最大长度出现的次数
            if(m > max){
                max = m;
                times = 1;
            }else if(m == max){
                times ++;
            }
        }
        a_t[0][i] = max;
        a_t[1][j] = times;
    }
    /*
    用一个二维数组，第一行为该位置最长可以组成的序列长度，第二行代表该长度的序列个数
    */
    for(i = 0;i<2;i++){
        for(j = 0;j<n;j++){
            printf("%d ",a_t[i][j]);
        }
        puts("");
    }
    return 0;
}