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)```

{"mode":"full","isActive":false}

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

}
```

{"mode":"full","isActive":false}

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

{"mode":"full","isActive":false}

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

```

{"mode":"full","isActive":false}