当前位置:网站首页>Programming question - find the number of the longest increasing subsequence

Programming question - find the number of the longest increasing subsequence

2020-12-07 15:49:59 osc_ djoqamxp

The number of longest increasing subsequences

  • Source : Today's headline contains a programming question
  • subject : There's an unordered array , Now we need you to find the longest increasing subsequence number .

eg1: 1 2 4 3 5
The longest increasing subsequence is 1 2 4 5 and 1 2 3 5, So we should output 2.
eg2:1 1 1 1 1
Output 5, That is 5 A length of 1 Of 1


Ideas

We subscript from the array as 0 Start ,0 When subscribing , The maximum length containing the current position can only be 1, And the times are 1, Subscript to be 1 when , contain 1 The longest increasing sequence of subscripts requires and 0 Place to compare ,a[1]> a[0] Then the length will naturally be updated to 2, The number of occurrences is given an initial value 1, If less than or equal to , So it includes 1 The subscript string is a[1] In itself , The longest is 1, The number of occurrences is 1, Then judge the subscript in this way .

This , Obviously, the idea of dynamic programming is to be used , And this is not simple DP, But the result of the front position , It's not just up to him to decide , It's up to all of them to decide , So sort out the ideas :

use a[] = 1 2 4 3 5 For example .
Now we need an auxiliary array a_t[2][len(a)]. The first line of the array , It ends with the number of the subscript position , The length of the longest increment string . Why do you have to end with that position , Because we don't know , Maybe it seems that choosing this subscript makes the string length smaller , But I'm not sure if this length will exceed the value of not selecting the subscript in the future . Second line of array , This is the number of strings of this length .
So in the end a_t = {
1,2,3,3,4
1,1,1,1,2
}
The longest string is 4 Length , There is 2 Time .





#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 Represents the current length , At least 1
            if(a[i] > a[j]){
                m = a_t[0][j] + 1;
                // If the current one is bigger than the previous one , It will increase the length 
            }
            else if(a[i] == a[j]){
                // Equality does not change the maximum length 
                m  = a_t[0][j];
            }
            // Update the maximum length and the number of times the maximum length appears 
            if(m > max){
                max = m;
                times = 1;
            }else if(m == max){
                times ++;
            }
        }
        a_t[0][i] = max;
        a_t[1][j] = times;
    }
    /*
     Use a two-dimensional array , The first line is the length of the longest sequence that the position can be composed of , The second line represents the number of sequences of that length 
    */
    for(i = 0;i<2;i++){
        for(j = 0;j<n;j++){
            printf("%d ",a_t[i][j]);
        }
        puts("");
    }
    return 0;
}

版权声明
本文为[osc_ djoqamxp]所创,转载请带上原文链接,感谢
https://chowdera.com/2020/12/20201207153955851q.html