Finding the Length of the Longest Increasing Subsequence in an Array


Introduction:

In this article, we will explore an efficient algorithm to find the length of the longest increasing subsequence in an array. We'll walk through a step-by-step implementation of the algorithm in C++. Let's dive in!

 


Problem Statement:

Given an array of integers, we need to find the length of the longest increasing subsequence. An increasing subsequence is a sequence of array elements in which each element is greater than the previous one. Our goal is to find the longest increasing subsequence and return its length.

 

Approach:

To solve this problem efficiently, we can use the Dynamic Programming concept known as the Longest Increasing Subsequence (LIS) algorithm. The main idea behind this algorithm is to build a dynamic array, `tail`, to store the increasing subsequence as we iterate through the given array.

 

Algorithm:

  1. Create an array `tail` of size `n`, where `n` is the length of the input array, to store the increasing subsequence. Initialize `len` to 1, as the minimum length of any subsequence is 1.

 

  1. Assign the first element of the input array to `tail[0]`.

 

  1. Iterate over the remaining elements of the array from index 1 to `n-1`.

 

  1. For each element `a[i]`, compare it with the last element of `tail` (i.e., `tail[len-1]`).

   - If `a[i]` is greater than `tail[len-1]`, it can be appended to the current increasing subsequence. Assign `a[i]` to `tail[len]` and increment `len` by 1.

   - If `a[i]` is not greater than `tail[len-1]`, find the index `c` using the `ceilIdx` function, which gives the index of the smallest element in `tail` greater than or equal to `a[i]`. Update `tail[c]` with `a[i]`.

 

  1. After iterating over all the elements, `len` will hold the length of the longest increasing subsequence.

 

  1. Return `len` as the result.

 

Helper Function: `ceilIdx`

The `ceilIdx` function is a helper function used to find the index of the smallest element in the `tail` array that is greater than or equal to a given `key`. It uses a binary search approach to efficiently search for the index.

Example:

Let's consider the array: {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}.

 

Algorithm and Cases:

The LIS algorithm consists of three cases that determine how to construct the active lists during iteration:

 

Case 1: Start a New Active List:

 

If A[i] is the smallest among all end candidates of the active lists, we start a new active list of length 1.

For example, when A[0] = 0, there are no active lists, so we create one: 0.

Case 2: Clone and Extend:

 

If A[i] is the largest among all end candidates of the active lists, we clone the largest active list and extend it by A[i].

For example, when A[1] = 8, we clone the existing active list and extend it: 0, 8.

Case 3: Find, Clone, Extend, and Discard:

 

If A[i] is in between the smallest and largest end elements of the active lists, we find a list with the largest end element that is smaller than A[i]. We then clone and extend this list by A[i]. We discard all other lists of the same length as the modified list.

For example, when A[2] = 4, we clone the list ending at 0, extend it with 4, and discard the list ending at 8: 0, 4.

Let's visualize the step-by-step construction of the active lists using the provided example:

 

0, 8.

0, 4.

0, 4, 12.

0, 2.

0, 2, 10.

0, 2, 6.

0, 2, 6, 14.

0, 1.

0, 2, 6, 9.

0, 1, 5.

0, 2, 6, 9, 13.

0, 1, 3.

0, 2, 6, 9, 11.

0, 1, 3, 7.

0, 2, 6, 9, 11, 15.

 

Code:

```cpp

#include <iostream>

using namespace std;

 

class Solution {

public:

    // Function to find the index of the smallest element in the 'tail' array greater than or equal to 'key'

    int ceilIdx(int tail[], int l, int r, int key) {

        while (r > l) {

            int m = l + (r - l) / 2;

            if (tail[m] >= key)

                r = m;

            else

                l = m + 1;

        }

 

        return r;

    }

 

    // Function to find the length of the longest increasing subsequence

    int longestSubsequence(int n, int a[]) {

        int tail[n];

        int len = 1;

 

        tail[0] = a[0];

 

        for (int i = 1; i < n; i++) {

            if (a[i] > tail[len - 1]) {

                tail[len] = a[i];

                len++;

            }

            else {

                int c = ceilIdx(tail, 0, len - 1, a[i]);

                tail[c] = a[i];

            }

        }

 

        return len;

    }

};

 

int main() {

    int n;

    cin >> n;

    int a[n];

 

    // Taking input for the array elements

    for (int i = 0; i < n; i++)

        cin >> a[i];

 

    Solution ob;

    cout << ob.longestSubsequence(n, a) << endl;

 

    return 0;

}

```

 

Conclusion:

In this article, we discussed an efficient approach to finding the length of the longest increasing subsequence in an array using the LIS algorithm. We walked through the step-by-step implementation of the algorithm in C++. By using the dynamic programming concept, we were able to achieve an optimal solution to the problem. I hope you found this article helpful in understanding the concept and implementation.

Previous Post Next Post