Programming question - find the number of the longest increasing subsequence

2020-12-07 15:49:59

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> a 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 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[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[n];
memset(a_t,0,2*n*4);

a_t = 1;
a_t = 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[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[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[i] = max;
a_t[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;
}

https://chowdera.com/2020/12/20201207153955851q.html