Longest Increasing Subsequence in Java

The longest increasing subsequence (LIS) problem is a classical problem in computer science. It involves finding the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. Below is a Java program that solves this problem using dynamic programming.

Program Structure

The program uses a dynamic programming approach to find the LIS. It maintains an array dp where dp[i] represents the length of the longest increasing subsequence ending at index i. The program iterates through the array, updating the dp values based on previous values to determine the LIS.

Java Code

/**
 * Java program to find the Longest Increasing Subsequence (LIS) in an array.
 */
public class LongestIncreasingSubsequence {

    /**
     * Method to find the length of the longest increasing subsequence.
     * 
     * @param arr the input array
     * @return the length of the longest increasing subsequence
     */
    public static int longestIncreasingSubsequence(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        
        // Array to store the length of LIS up to each element
        int[] dp = new int[arr.length];
        
        // Initialize the dp array with 1, as the minimum length of LIS is 1
        for (int i = 0; i < dp.length; i++) {
            dp[i] = 1;
        }
        
        // Compute the dp values
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) { if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                }
            }
        }
        
        // Find the maximum value in dp array
        int lisLength = 0;
        for (int i = 0; i < dp.length; i++) {
            lisLength = Math.max(lisLength, dp[i]);
        }
        
        return lisLength;
    }
    
    public static void main(String[] args) {
        int[] arr = {10, 22, 9, 33, 21, 50, 41, 60, 80};
        
        int length = longestIncreasingSubsequence(arr);
        System.out.println("Length of the Longest Increasing Subsequence is: " + length);
    }
}
    

Explanation

1. Initialization: The dp array is initialized to 1, as the smallest possible LIS for any element is itself.
2. Dynamic Programming Computation: For each element in the array, the program checks all previous elements to update the dp value, considering whether the current element can extend the LIS ending at previous elements.
3. Finding the Result: After filling the dp array, the program finds the maximum value in dp, which represents the length of the LIS.

Running the Program

To run this Java program, save the code in a file named LongestIncreasingSubsequence.java. Compile it using javac LongestIncreasingSubsequence.java and run it using java LongestIncreasingSubsequence.