This article describes the Java implementation of the longest subsequence algorithm for arrays. Share it for your reference, as follows:
Problem: Given an array of length N, find the longest monotonic autoincrement sub-sequence (not necessarily continuous, but the order cannot be messed up). For example: Given an array of length A{1, 3, 5, 2, 4, 6, 7, 8} with length 8, then its longest monotonic amplicon sequence is {1, 2, 4, 6, 7, 8} and its length is 6.
Idea 1: When you see the question at first, many people will definitely think of LCS at the first time. First sort the array into a new array, and then use the new array and the original array to find LCS to get the answer. Many people can imagine this solution, so I won’t go into details.
Idea 2: According to the idea of Idea 1, you still have to use DP when you finally find LCS. Why don’t we use DP to solve it directly? For the array arr, we traverse the array from behind to front, and find the longest subsequence when the subsequence ends with arr[i] , and then take the maximum value therein. You can get the longest subsequence of the entire array. So how to find the longest subsequence ending with arr[i] ? This is converted into a DP problem. To require the longest subsequence of arr[i] , you only need to find the longest subsequence of arr[i-1] . That is: max{arr[i]}=max{arr[i-1]}+1 .
Java implementation code:
public class arrDemo { public static void main(String[] args) { // int[] arr = {89, 256, 78, 1, 46, 78, 8}; int[] arr = { 1, 3, 5, 2, 4, 6, 7, 8 }; // int[] arr = {6, 4, 8, 2, 17}; int max = 0; int maxLen = arr.length; // traverse the array from behind to forward, and find the longest subsequence length when ending with arr[i] for (int i = arr.length - 1; i > 0; i--) { int[] newArr = new int[i]; System.arraycopy(arr, 0, newArr, 0, i); int currentLength = 1 + dp(newArr, arr[i]); if (currentLength > max) max = currentLength; // The longest length of the longest subsequence is the length of the original array, // Because we do not need to find the element of the longest subsequence, we directly end the loop to reduce the time overhead if (max == maxLen) break; } System.out.println(max); } public static int dp(int[] arr, int end) { // Recursive end condition if (arr.length == 1) { // If less than end, it is included in the subsequence, the length of the subsequence +1 if (arr[0] <= end) return 1; else return 0; } // traverse the array and find the element position closest to end and <=end i for (int i = arr.length - 1; i >= 0; i--) { if (arr[i] <= end) { // truncate the array from i, and form a new array to arr[0] to arr[i-1] to continue recursively finding the length int[] newArr = new int[i]; System.arraycopy(arr, 0, newArr, 0, i); // Calculate the longest subsequence when containing arr[i] and the longest subsequence when not containing arr[i], respectively, and take the maximum value int containsLen = dp(newArr, arr[i]) + 1; int notContainLen = dp(newArr, end); return containsLen > notContainLen ? containsLen : notContainLen; } } // If no smaller than end is found, the return length is 0 return 0; }}Running results:
6
My method may take up a lot of space because multiple new arrays are opened in the middle, but I don't think it's a lot - - I haven't counted it. If there is anything wrong, please correct it.
For more information about Java algorithms, readers who are interested in this site can view the topics: "Java Data Structure and Algorithm Tutorial", "Summary of Java Operation DOM Node Tips", "Summary of Java File and Directory Operation Tips" and "Summary of Java Cache Operation Tips"
I hope this article will be helpful to everyone's Java programming.