Geek asks and answers

The longest growing subsequence from each item

Given the list {x_i}, I want to find the longest ascending subsequence starting from each element, so that the original element is included in the subsequences.

The obvious way would be to make a regular algorithm with the largest increase in the subsequence on each element, providing O (n ^ 2 logn). Could it be beaten?

+3
source share
3 answers

You can use DP and transfer it to O (n ^ 2).

Let the input be x1, x2, ..., xn

Let f1, f2, ..., fn be the length of the longest ascending sequence, starting from the ith element. Initialize all of them to 1.

Now

for i = n-1, n-2, .... , 1:
    for j = i,i+1,...,n:
        if x[i]<x[j]:
            fi=max(fi, fj+1)

, g1, g2,..., gn, gi - , . gis NULL.

for i = n-1, n-2, .... , 1:
    for j = i,i+1,...,n:
        if x[i]<x[j]:
            if fi<fj+1:
                fi=fj+1
                gi=j

gs, , , , .

+2

, . - . , , .

: , . , , , , .

O (N ^ 2), .

+1

int main(){

int arr[]={1,10,5,12,17,18,19};
int t[]={1,0,0,0,0,0,0};
int i,j;
vector<int>v[7];
v[0].push_back(1);       
for(i =1;i<7;i++){

    for(j =0;j<i;j++){
          if(arr[j]<arr[i]){

             if(t[j]>=t[i]){
                 t[i]=t[j]+1;
                 v[i].push_back(arr[j]);
             }
          }
     }
     if(i==j){
        v[i].push_back(arr[i]);
     }
}

for(i=0;i<7;i++){
    for(j=0;j<v[i].size();j++){
        cout<<v[i][j]<<" ";
    }
    cout<<endl;
}


return 0;

} >

++, N ^ 2. ( ) , . nlogn order.I , . , , .

0

More articles:


All Articles