Article From:https://www.cnblogs.com/javaStudy947/p/9217407.html

Title:

Given a sequence consisting of N integers, find the longest length in all non decreasing subsequences. For example, {A_n}=3,18,7,14,10,12,23,41,16,24, where 3,18,23,41 is a sequence of 4 non decreasing subsequences.

But 3,7,10,12,16,24 is a subsequence of 6 length.

It is found that if A (I) > =A (i-1), the length of the longest non descending sequence ending with A (I) should be the longest non decreasing sequence ending with A (i-1) plus 1. If it is less than, then look forward from A (i-1) until it satisfies A (I) > A (J), at this time.

The longest non descending sequence length is the length ending with A (J) plus 1. Create an array to record the longest subsequence length at the end of each element, and finally output the maximum value. Time complexity is O (n^2)

public class LongestNondescendantSequence {
    public static void main(String[] args)
    {
        int[] arr=new int[] {3,18,7,14,10,12,23,41,16,24};
        LNS(arr);
    }
    public static void LNS(int[] arr)
    {
        int[] a=new int[arr.length];
        int max=0;
        //The length of a single element does not decrease. The length of the subsequence can not be less than 1 and initialized to 1.
        for(int i=0;i<arr.length;i++)
            a[i]=1;
        for(int i=1;i<arr.length;i++)
        {
            //If the current element is greater than the last element, the length of the current element ending does not decrease by 1.
            if(arr[i]>=arr[i-1])
                a[i]=a[i]+a[i-1];
            //Otherwise, the former element looks for the element less than the current element from the back, and the length of the non descent subsequence that ends with the current element is added 1 to the length of the non descent subsequence of the found element.
            else
            {
                for(int j=i-1;j>=0;j--)
                {
                    if(arr[j]<arr[i])
                    {
                        a[i]=a[j]+1;
                        break;
                    }
                }
            }
        }
        //Maximum print length
        for(int i=0;i<a.length;i++)
        {
            if(a[i]>max)
                max=a[i];    
        }
        System.out.print(max);            
    }
}

Print results

 

Leave a Reply

Your email address will not be published. Required fields are marked *