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