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:
- 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.
- Assign the first element of the input array to `tail[0]`.
- Iterate over the remaining elements of the array from index 1 to `n-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]`.
- After iterating over all the elements, `len` will hold the length of the longest increasing subsequence.
- 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.
