Hello! Today, we will discuss one of the frequently asked problems in Java coding tests, which is finding the ‘Longest Increasing Subsequence (LIS)’. This problem involves finding the length of the longest subsequence of selected elements in a given sequence that are in increasing order. It may seem like a complex algorithm problem, but it can be solved through efficient approaches that can help improve your scoring in coding tests.<\/p>\n
There is a given array of integers. Write a program that returns the length of the longest increasing subsequence in this array. For example:<\/p>\n
Input: [10, 9, 2, 5, 3, 7, 101, 18]\nOutput: 4\nExplanation: The increasing subsequence is [2, 3, 7, 101], which has a length of 4.<\/code><\/pre>\nSolution Method<\/h2>\n
There are several approaches to solving this problem. One of the most intuitive methods is to use Dynamic Programming<\/strong>. Using this method, the problem can be solved with a time complexity of O(n^2). Moreover, by further optimizing this problem, it can also be solved with a time complexity of O(n log n). In this article, we will cover both methods.<\/p>\n1. Method using Dynamic Programming<\/h3>\n
First, let’s look at how to solve the problem using Dynamic Programming. The process is as follows:<\/p>\n
\n- Given an array of length n, create a DP array of size n. Each element of the DP array stores the length of the longest increasing subsequence up to that index.<\/li>\n
- Set all initial values of the DP array to 1. (Each element can have at least itself as a subsequence.)<\/li>\n
- Use a nested loop to check each element and update the length of the increasing subsequence by comparing it with previous elements.<\/li>\n
- Finally, return the maximum value from the DP array.<\/li>\n<\/ol>\n
Now let’s implement this in Java.<\/p>\n
public class LongestIncreasingSubsequence {\n\n public static int lengthOfLIS(int[] nums) {\n if (nums == null || nums.length == 0) {\n return 0;\n }\n \n int n = nums.length;\n int[] dp = new int[n];\n \n \/\/ Initialize the length of all sequences to 1\n for (int i = 0; i < n; i++) {\n dp[i] = 1;\n }\n \n for (int i = 1; i < n; i++) {\n for (int j = 0; j < i; j++) {\n if (nums[i] > nums[j]) {\n dp[i] = Math.max(dp[i], dp[j] + 1);\n }\n }\n }\n \n \/\/ Find the maximum value in the DP array\n int maxLength = 0;\n for (int length : dp) {\n maxLength = Math.max(maxLength, length);\n }\n \n return maxLength;\n }\n\n public static void main(String[] args) {\n int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};\n System.out.println(\"Length of the longest increasing subsequence: \" + lengthOfLIS(nums));\n }\n}<\/code><\/pre>\nCode Analysis<\/h4>\n
The above code proceeds as follows:<\/p>\n
\n- Returns 0 if the given array is null or has a length of 0.<\/li>\n
- Initializes the DP array so that all values are 1.<\/li>\n
- Compares each element with a nested loop to update the length of the increasing subsequence.<\/li>\n
- Finds and returns the length of the longest subsequence from the DP array.<\/li>\n<\/ul>\n
2. O(n log n) Method<\/h3>\n
Next, let’s explore the O(n log n) method. This method can solve the problem more efficiently through Binary Search. The algorithm follows these steps:<\/p>\n
\n- Create an empty list.<\/li>\n
- Iterate over each element of the input array. If it is greater than the last element of the list, add it to the list.<\/li>\n
- If it is less than or equal to the last element of the list, find its position in the list using binary search, then replace the element at that position.<\/li>\n
- The length of the list will ultimately be the length of the longest increasing subsequence.<\/li>\n<\/ol>\n
Now, let’s implement this in Java.<\/p>\n
import java.util.ArrayList;\nimport java.util.List;\n\npublic class LongestIncreasingSubsequenceBinarySearch {\n\n public static int lengthOfLIS(int[] nums) {\n List lis = new ArrayList<>();\n \n for (int num : nums) {\n int index = binarySearch(lis, num);\n if (index == lis.size()) {\n lis.add(num);\n } else {\n lis.set(index, num);\n }\n }\n \n return lis.size();\n }\n\n private static int binarySearch(List lis, int num) {\n int left = 0, right = lis.size();\n\n while (left < right) {\n int mid = left + (right - left) \/ 2;\n if (lis.get(mid) < num) {\n left = mid + 1;\n } else {\n right = mid;\n }\n }\n \n return left;\n }\n\n public static void main(String[] args) {\n int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};\n System.out.println(\"Length of the longest increasing subsequence: \" + lengthOfLIS(nums));\n }\n}<\/code><\/pre>\nCode Analysis<\/h4>\n
The analysis of the code above is as follows:<\/p>\n