1. Introduction

The Longest Increasing Subsequence (LIS) problem is a well-known challenge in the algorithms domain. Given a sequence of numbers, the goal is to find the length of the longest subsequence that is strictly increasing. A subsequence is derived from the original sequence by deleting some elements, possibly none, without changing the order of the remaining elements. The problem has an efficient solution using dynamic programming.

2. Program Steps

1. Initialize an array lis of size n (length of the given sequence) where each element is set to 1. This array will store the LIS ending at each index.

2. Using a nested loop, compare elements of the sequence and update the lis array based on previous computations.

3. Return the maximum value in the lis array, which represents the length of the LIS.

4. In the main method, input an example sequence and compute its LIS.

3. Code Program

class LongestIncreasingSubsequence {

    public static int lis(int[] arr) {
        int n = arr.length;
        int[] lis = new int[n];
        int max = 0;

        for (int i = 0; i < n; i++) {
            lis[i] = 1;
        }

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j] && lis[i] < lis[j] + 1) {
                    lis[i] = lis[j] + 1;
                }
            }
        }

        for (int 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};
        System.out.println("Length of LIS is: " + lis(arr));
    }
}
x

Output:

Length of LIS is: 6

4. Step By Step Explanation

1. The method lis calculates the longest increasing subsequence of a given sequence.

2. We first initialize the lis array with all values set to 1 because a single element is an increasing sequence of length 1.

3. Using nested loops, for every element arr[i], we compare it with all elements before it. If arr[i] is greater than a previous element arr[j] and the length of LIS ending at arr[i] is less than the length of LIS ending at arr[j] plus one, then update lis[i].

4. After constructing the lis array, we extract the maximum value, which gives us the length of the longest increasing subsequence.

5. The main method offers a sample sequence. The longest increasing subsequence for this sequence is: 10, 22, 33, 50, 60, 80, hence the length 6.