Longest non-descending subsequence (O(nlogn)) (Offer harvest)

The title

If inscribe

Train of thought

The idea is to maintain an array ends that records the minimum value of the last element of a subsequence of length K. Sounds abstract, so let’s go through the whole process manually.

Assuming array a={2,9,4,27,29,15,7}, let length represent the length of the longest non-descending subsequence currently found. Initial length=1, ends[1]=2

I =1, length=2, ends[2]=9;

I =2, length=2, ends[2]=4, because 4 is easier than 9 to form a non-descending subsequence with the following number;

I =3, length=3, ends[3]=27;

I =4, length=4, ends[4]=29;

I =5, length=4, 15 can join ends[2]=4, and it is easier than ends[3]=27 to form a non-descending subsequence with the following number, so ends[3]=15;

I =6, length=4, end[3]=7.

As you can see, the whole algorithm is to find the first position in the ends that is greater than the current number. Ends [t-1]<=a[I], a[I] can be connected to the ends[t-1] to form a subsequence of length I, and a[I] can be connected to the ends[t-1] to form a subsequence of length I, and a[I] can be connected to the ends[t] to form a subsequence of length I. So let’s make a substitution. So the idea of the algorithm is greed plus dichotomy.

code

package com.iqiyi;

public class Test {
    public static void main(String[] args){
        int[] array=new int[] {2.9.4.27.29.15.7};
        int[] ends=new int[array.length+1];
        ends[1]=array[0];
        int length=1;
        for(int i=1; i<array.length; i++){int low=1;
            int high=length;
            while(low<high){
                int mid=(low+high)/2;
                if(ends[mid]<=array[i])
                    low=mid+1;
                else
                    high=mid;
            }
            if(ends[low]>array[i])
                ends[low]=array[i];
            else{ length++; ends[length]=array[i]; } } System.out.println(length); }}Copy the code