Hello Everyone,
Given an array of random numbers. Find longest increasing subsequence (LIS) in the array.
Below is code to find length of LIS,
#include <iostream>
#include <vector>
// Binary search (note boundaries in the caller)
int CeilIndex(std::vector< int >& v, int l, int r, int key)
{
while (r - l > 1) {
int m = l + (r - l) / 2;
if (v[m] >= key)
r = m;
else
l = m;
}
return r;
}
int LongestIncreasingSubsequenceLength(std::vector< int >& v)
{
if (v.size() == 0)
return 0;
std::vector< int > tail(v.size(), 0);
int length = 1; // always points empty slot in tail
tail[0] = v[0];
for ( size_t i = 1; i < v.size(); i++) {
// new smallest value
if (v[i] < tail[0])
tail[0] = v[i];
// v[i] extends largest subsequence
else if (v[i] > tail[length - 1])
tail[length++] = v[i];
// v[i] will become end candidate of an existing
// subsequence or Throw away larger elements in all
// LIS, to make room for upcoming grater elements
// than v[i] (and also, v[i] would have already
// appeared in one of LIS, identify the location
// and replace it)
else
tail[CeilIndex(tail, -1, length - 1, v[i])] = v[i];
}
return length;
}
int main()
{
std::vector< int > v{ 2, 5, 3, 7, 11, 8, 10, 13, 6 };
std::cout << "Length of Longest Increasing Subsequence is "
<< LongestIncreasingSubsequenceLength(v) << '\n' ;
return 0;
}
Output:
Length of Longest Increasing Subsequence is 6
Complexity:
The loop runs for N elements. In the worst case (what is worst case input?), we may end up querying ceil value using binary search (log i ) for many A[i].
Therefore, T(n) < O( log N! ) = O(N log N). Analyse to ensure that the upper and lower bounds are also O( N log N ). The complexity is THETA (N log N).