1. Introduction

The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. It’s important to note that the subsequence does not need to be contiguous, but it must maintain the same relative order.

2. Program Steps

1. Initialize an array lis with the length of the given sequence and fill it with 1s. This array will help track the length of the LIS ending at each index.

2. Iterate through the given sequence comparing elements.

3. For each pair of elements, check if increasing and update the lis value.

4. Return the maximum value from the lis array.

3. Code Program

public class LIS {
    static int longestIncreasingSubsequence(int arr[], int n) {
        int lis[] = new int[n];
        int i, j, max = 0;

        // Initialize LIS values for all indices
        for (i = 0; i < n; i++)
            lis[i] = 1;

        // Compute LIS values in bottom up manner
        for (i = 1; i < n; i++)
            for (j = 0; j < i; j++)
                if (arr[i] > arr[j] && lis[i] < lis[j] + 1)
                    lis[i] = lis[j] + 1;

        // Return the maximum value of lis[]
        for (i = 0; i < n; i++)
            if (max < lis[i])
                max = lis[i];

        return max;
    }

    public static void main(String[] args) {
        int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60, 80 };
        int n = arr.length;
        System.out.println("Length of the LIS is " + longestIncreasingSubsequence(arr, n));
    }
}

Output:

Length of the LIS is 6

4. Step By Step Explanation

1. The longestIncreasingSubsequence function calculates the length of the LIS for the given array.

2. We first initialize an array lis with ones. The value of lis[i] gives the length of the LIS ending at index i.

3. For each pair of indices (i, j), if arr[i] > arr[j] (i.e., the sequence is increasing) and the LIS ending at i is less than the LIS ending at j plus 1, then we update lis[i]. This step effectively builds upon previously computed LIS values.

4. Finally, we return the maximum value from the lis array, which represents the length of the overall LIS.

5. The main method initializes an array, calls longestIncreasingSubsequence, and prints the result.