HackerRank The Longest Increasing Subsequence problem solution

In this HackerRank The Longest Increasing Subsequence problem solution The task is to find the length of the longest subsequence in a given array of integers such that all elements of the subsequence are sorted in strictly ascending order. This is called the Longest Increasing Subsequence (LIS) problem.

This is one approach which solves this in quadratic time using dynamic programming. A more efficient algorithm which solves the problem in O(n log n) time is available here.

Given a sequence of integers, find the length of its longest strictly increasing subsequence.

Function Description

Complete the longestIncreasingSubsequence function in the editor below. It should return an integer that denotes the array’s LIS.

longestIncreasingSubsequence has the following parameter(s):

• arr: an unordered array of integers

HackerRank The Longest Increasing Subsequence problem solution in Python.

import sys

n = int(input())

class BTreeInterval():
    def __init__(self, n, max):
        self.intervals = [None] * (n + 1)
        self.intervals[0] = (0, max)
        self.current_max = 0
        self.num_max = max
    def get(self, num):
        
        return self.get1(num, self.current_max / 2, 0, self.current_max)
    def get1(self, num, i, fr, to):
        i = int(i)
        #print('intervals:{0} i: {1} from: {2} to: {3}'.format(self.intervals, i, fr, to))
        if fr == to:
            return i
        if num >= self.intervals[i][0] and num < self.intervals[i][1]:
            return i
        if num < self.intervals[i][0]:
            return self.get1(num, (fr + i - 1) / 2, fr, i - 1)
        else:
            return self.get1(num, (i + 1 + to) / 2, i + 1, to)
     
    def set(self, num, i):
        if self.current_max >= i and num >= self.intervals[i][0]:
            return False
        self.intervals[i-1] = (self.intervals[i-1][0], num)
        if i > self.current_max:
            self.current_max = i
            self.intervals[i] = (num, self.num_max)
        else:
            self.intervals[i] = (num, self.intervals[i][1])
        
        return True
        
nums = []

for _ in range(n):
    nums += [int(input())]
    

MAX = 100001

cache = [0] * MAX
local_max = 0

max = 1

btree = BTreeInterval(n, MAX)


for i in range(n):
    
    prev_val = btree.get(nums[i] - 1)
    #print('prev_val: {0} current_num: {1}'.format(prev_val, nums[i]) )
    flag = btree.set(nums[i], prev_val + 1)
    
    if flag and prev_val + 1 > max:
        max = prev_val + 1
#print(btree.intervals[0:(n+1)])            
print(max)

The Longest Increasing Subsequence problem solution in Java.

import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

public class LongestIncreasing {

    static int solve(int[] X) {

        
        int[] M = new int[X.length];
        Arrays.fill(M, -1);
        int L = 1;

        M[0] = X[0];

        for (int i=1; i<X.length; ++i) {
            int x = X[i];
            int lo = Arrays.binarySearch(M, 0, L, x);
            if (lo < 0)
                lo = - (lo + 1);

            int newL = lo + 1;

            M[newL-1] = x;

            if (newL > L)
                L = newL;

        }

        return L;
    }

    public static void main(String[] args) throws FileNotFoundException {

        Scanner sn = new Scanner(System.in);

        int N = sn.nextInt();
        int[] a = new int[N];

        for (int i=0; i<N; ++i)
            a[i] = sn.nextInt();
        System.out.println(solve(a));
    }


}

Problem solution in C++.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    int n;
    cin >> n;
    vector<int> data, m;
    m.push_back(-1);
    int l=0;
    for(int i=0; i<n; i++) {
        int elt;
        cin >> elt;
        data.push_back(elt);
        //Binary search
        int lo=1, hi = l;
        while(lo <= hi) {
            int mid = (lo+hi)/2;
            if(data[m[mid]] < data[i]) {
                lo = mid+1;
            } else {
                hi = mid-1;
            }
        }
        if(lo > l) {
            l++;
            m.push_back(i);
        } else {
            m[lo] = i;
        }
    }
    cout << l;
    
    return 0;
}

Problem solution in C.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

typedef long long int  ll_int ;

void LongestIncreasingSubsequence( ll_int *A , ll_int size ) ;
ll_int ceilIndex(ll_int *A , ll_int *minEndingIndex , ll_int l , ll_int r , ll_int key )  ;


int main() {

ll_int  *A, i = 0 ;
ll_int size = 0 ;    
    
scanf("%lld",&size ) ;
    
 A = malloc( size * sizeof(ll_int ))    ;
 
    while( i < size )
        scanf("%lld",&A[i++]) ;
    
     LongestIncreasingSubsequence( A ,  size ) ;
    
    return 0;

}

 

void LongestIncreasingSubsequence( ll_int *A , ll_int size ) {
    
 ll_int i = 0, j = 0 , len = 1, pos    ;   
 ll_int *minEndingIndex  = malloc(size*sizeof(ll_int)) ;    
 ll_int *PrevIndex = malloc(size*sizeof(ll_int))  ;
    
  for( j = 0 ; j < size ; j++ )
       minEndingIndex[j] = 0 ;
  
    for( j = 0 ; j < size ; j++ )
       PrevIndex[j] = -1 ;
    
    
 while( ++i <  size ) {
     
     if(  A[i] < A[ minEndingIndex[0] ]  ) {
         
          minEndingIndex[0] = i ;
          continue ;
     }
     
     
     if( A[i] > A[ minEndingIndex[len-1] ] ) {
         
         PrevIndex[i] = len ;
         minEndingIndex[len++] = i ;
         
         continue ;    
     }
     
     
     pos = ceilIndex( A , minEndingIndex , (ll_int) -1, len - 1 , A[i] ) ;
     minEndingIndex[pos]= i ;
     PrevIndex[i] = pos - 1 ;
     
 } 
    
printf("%lld",len) ;

}


ll_int ceilIndex(ll_int *A , ll_int *minEndingIndex , ll_int l , ll_int r , ll_int key ) {

    ll_int m ;
    
    while( r - l  > 1 ) {
        
        m =  l + ( r - l ) / 2 ;
        
        if( A[ minEndingIndex[m] ] > key  || A[minEndingIndex[m]] == key )
           r = m ;
        else 
           l = m ;
        
    }
    
    
    return r ;
}