Algorithm C++ programming

C++ Programming – Longest Monotonically Increasing Subsequence Size

Given an array of random numbers, find longest monotonically increasing subsequence (LIS) in the array.If you want to understand the O(NlogN) approach.

Given an array of random numbers, find longest monotonically increasing subsequence (LIS) in the array.

If you want to understand the O(NlogN) approach, it’s explained very clearly here.

In this post, a simple and time saving implementation of O(NlogN) approach using stl is discussed. Below is the code for LIS O(NlogN)

C++ Program
// A simple C++ implementation to find LIS
#include<iostream>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
 
// Return length of LIS in arr[] of size N
int lis(int arr[], int N)
{
    int i;
    set<int> s;
    set<int>::iterator k;
    for (i=0; i<N; i++)
    {
        // Check if the element was actually inserted
        // An element in set is not inserted if it is
        // already present. Please see
        // http://www.cplusplus.com/reference/set/set/insert/
        if (s.insert(arr[i]).second)
        {
            // Find the position of inserted element in iterator k
            k = s.find(arr[i]);
 
            k++;  // Find the next greater element in set
 
            // If the new element is not inserted at the end, then
            // remove the greater element next to it (This is tricky)
            if (k!=s.end()) s.erase(k);
        }
    }
 
    // Note that set s may not contain actual LIS, but its size gives
    // us the length of LIS
    return s.size();
}
 
int main()
{
    int arr[] = {8, 9, 12, 10, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << lis(arr, n)<< endl;
}

Output:

4

 

READ  C++ Programming - Check if an array can be divided into pairs whose sum is divisible by k

About the author

Venkatesan Prabu

Venkatesan Prabu

Wikitechy Founder, Author, International Speaker, and Job Consultant. My role as the CEO of Wikitechy, I help businesses build their next generation digital platforms and help with their product innovation and growth strategy. I'm a frequent speaker at tech conferences and events.

Add Comment

Click here to post a comment