欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-02-24 23:46:34
...

最长递增子序列的数量

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

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;
}