Java Coding Test Course, Finding the Longest Increasing Subsequence

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.

Problem Description

There is a given array of integers. Write a program that returns the length of the longest increasing subsequence in this array. For example:

Input: [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Explanation: The increasing subsequence is [2, 3, 7, 101], which has a length of 4.

Solution Method

There are several approaches to solving this problem. One of the most intuitive methods is to use Dynamic Programming. 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.

1. Method using Dynamic Programming

First, let’s look at how to solve the problem using Dynamic Programming. The process is as follows:

  1. 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.
  2. Set all initial values of the DP array to 1. (Each element can have at least itself as a subsequence.)
  3. Use a nested loop to check each element and update the length of the increasing subsequence by comparing it with previous elements.
  4. Finally, return the maximum value from the DP array.

Now let’s implement this in Java.

public class LongestIncreasingSubsequence {

    public static int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int n = nums.length;
        int[] dp = new int[n];
        
        // Initialize the length of all sequences to 1
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        
        // Find the maximum value in the DP array
        int maxLength = 0;
        for (int length : dp) {
            maxLength = Math.max(maxLength, length);
        }
        
        return maxLength;
    }

    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println("Length of the longest increasing subsequence: " + lengthOfLIS(nums));
    }
}

Code Analysis

The above code proceeds as follows:

  • Returns 0 if the given array is null or has a length of 0.
  • Initializes the DP array so that all values are 1.
  • Compares each element with a nested loop to update the length of the increasing subsequence.
  • Finds and returns the length of the longest subsequence from the DP array.

2. O(n log n) Method

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:

  1. Create an empty list.
  2. Iterate over each element of the input array. If it is greater than the last element of the list, add it to the list.
  3. 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.
  4. The length of the list will ultimately be the length of the longest increasing subsequence.

Now, let’s implement this in Java.

import java.util.ArrayList;
import java.util.List;

public class LongestIncreasingSubsequenceBinarySearch {

    public static int lengthOfLIS(int[] nums) {
        List lis = new ArrayList<>();
        
        for (int num : nums) {
            int index = binarySearch(lis, num);
            if (index == lis.size()) {
                lis.add(num);
            } else {
                lis.set(index, num);
            }
        }
        
        return lis.size();
    }

    private static int binarySearch(List lis, int num) {
        int left = 0, right = lis.size();

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (lis.get(mid) < num) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left;
    }

    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println("Length of the longest increasing subsequence: " + lengthOfLIS(nums));
    }
}

Code Analysis

The analysis of the code above is as follows:

  • Create an empty list to store the longest increasing subsequence.
  • Iterate through each element and use binary search to find the position for insertion.
  • If it is less than the last element of the list, replace the element at that position.
  • Return the length of the list to provide the length of the longest increasing subsequence.

Conclusion

Today, we learned two ways to solve the ‘Longest Increasing Subsequence’ problem using Java. We solved this problem using the O(n^2) approach with Dynamic Programming and the O(n log n) method using Binary Search. These two approaches can be effectively utilized in coding tests.

We hope this helps you in preparing for job interviews and coding tests. Thank you!