## 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`.

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, 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 = 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 = 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 = a;

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.