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.

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)

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 ;
}