In this post, we will solve HackerRank The Longest Increasing Subsequence Game Problem Solution.
An Introduction to the Longest Increasing Subsequence Problem
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.
For example, the length of the LIS for [15, 27, 14, 38, 26, 55, 46, 65, 85] is 6 since the longest increasing subsequence is [15, 27, 38, 55, 65, 85].
This is one approach which solves this in quadratic time using dynamic programming. A more efficient algorithm which solves the problem in O(nlogn) 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
Output Format
Print a single line containing a single integer denoting the length of the longest increasing subsequence.
Sample Input 0
5 2 7 4 3 8
Sample Output 0
3
Explanation 0
In the array arr = [2, 7, 4, 3, 8], the longest increasing subsequence is [2, 7, 8]. It has a length of 3.
The Longest Increasing Subsequence C Solution
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int A[1000000],lis[1000000];
int CeilIndex(int l, int r, int key) {
int m;
while( r - l > 1 ) {
m = l + (r - l)/2;
if(lis[m]>=key)
r=m;
else
l=m;
}
return r;
}
int Lis_len(int size) {
// Add boundary case, when array size is on
int len; // always points empty slot
lis[0] = A[0];
len = 1;
for( int i = 1; i < size; i++ ) {
if( A[i] < lis[0] )
// new smallest value
lis[0] = A[i];
else if( A[i] > lis[len-1] )
// A[i] wants to extend largest subsequence
lis[len++] = A[i];
else
// A[i] wants to be current end candidate of an existing subsequence
// It will replace ceil value in tailTable
lis[CeilIndex(-1, len-1, A[i])] = A[i];
}
return len;
}
int main() {
int t,n,i;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&A[i]);
}
t=Lis_len(n);
printf("%d\n",t);
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
return 0;
}The Longest Increasing Subsequence C++ Solution
#include <bits/stdc++.h>
using namespace std;
#define _p(...) (void)printf(__VA_ARGS__)
#define forr(x,arr) for(auto&& x:arr)
#define _overload3(_1,_2,_3,name,...) name
#define _rep2(i,n) _rep3(i,0,n)
#define _rep3(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,_rep3,_rep2,)(__VA_ARGS__)
#define _rrep2(i,n) _rrep3(i,0,n)
#define _rrep3(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2,)(__VA_ARGS__)
#define ALL(x) (x).begin(), (x).end()
#define BIT(n) (1LL<<(n))
#define SZ(x) ((int)(x).size())
#define fst first
#define snd second
typedef vector<int> vi;typedef vector<vi> vvi;typedef pair<int,int> pii;typedef vector<pii> vpii;
typedef long long ll;
int lis(const vector<int>& a) {
int n = a.size();
const int inf = numeric_limits<int>::max();
vector<int> dp(n, inf);
for (int i = 0; i < n; i++) {
*lower_bound(dp.begin(), dp.end(), a[i]) = a[i];
}
return distance(dp.begin(), lower_bound(dp.begin(), dp.end(), inf));
}
void Main() {
int N;
scanf("%d", &N);
vi A(N);
rep(i, N) scanf("%d", &A[i]);
_p("%d\n", lis(A));
}
int main() { cin.tie(0); ios::sync_with_stdio(false); Main(); return 0; }The Longest Increasing Subsequence C Sharp Solution
using System;
using System.Linq;
using System.Collections.Generic;
using System.IO;
class Solution {
/* N*N sln relies on checking at each point for bext MIS (monotonically increasing seq)
static void Main(String[] args) {
int N = int.Parse(Console.ReadLine());
int[]L = new int[N];
int[] a = new int[N];
for (int i=0; i<N; i++) {
a[i]= int.Parse(Console.ReadLine());
L[i]=1;
}
int maxLen = 1;
for (int i=1; i<N; i++) {
for (int j=0; j<i; j++) {
if (a[j]<a[i] && L[j] >= L[i]) {
//Console.WriteLine("{0} {1} {2} {3}",a[j],a[i], L[j], L[i]);
L[i]=L[j]+1;
}
}
if (L[i] > maxLen) {
maxLen = L[i];
}
}
Console.WriteLine(maxLen);
}
*/
//NlogN soln
static void Main(String[] args)
{
int N = int.Parse(Console.ReadLine()); //num elems
int[] a = new int[N];
for (int i = 0; i < N; i++)
{
a[i] = int.Parse(Console.ReadLine());
}
DetectMIS(a);
Console.ReadLine();
}
private static void DetectMIS(int[] a)
{
int[] E = new int[a.Count()];
for (int i = 0; i < a.Count(); i++)
{
E[i] = Int32.MaxValue;
}
for (int i = 0; i < a.Count(); i++)
{
//since the idea is not increasing seq but STRICTLY increasing seq - dont add it exists,
var idx = Array.BinarySearch(E, a[i]); //insight E is already sorted in increasing order!
if (idx < 0)
{
//not found - next larger len formed at where it would have been inserted
var idx2 = ~idx; //where it would go
E[idx2] = a[i];
//Console.WriteLine("Processing {0} E[{1}]({2} => {3})", a[i], idx2, E[idx2], a[i]);
}
}
//print sln
for (int i = a.Count() - 1; i > -1; i--)
{
if (E[i] != Int32.MaxValue)
{
Console.WriteLine(i + 1);
break;
}
}
}
}The Longest Increasing Subsequence Java Solution
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
int n = reader.nextInt();
int[] array = new int[n];
for(int i = 0 ; i < n; i++ )
{
array[i] = reader.nextInt();
}
System.out.println(getLengthOfLIS(array));
}
public static int getLengthOfLIS(int[] array)
{
TreeSet<Integer> s = new TreeSet<Integer>();
for( int i = 0 ; i < array.length ; i++)
{
if( s.add(array[i]) )
{
if( array[i] != s.last() )
{
s.remove(s.higher(array[i]));
}
}
}
return s.size();
}
}The Longest Increasing Subsequence JavaScript Solution
'use strict';
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', _ => {
inputString = inputString.replace(/\s*$/, '')
.split('\n')
.map(str => str.replace(/\s*$/, ''));
main();
});
function readLine() {
return inputString[currentLine++];
}
// Complete the longestIncreasingSubsequence function below.
function longestIncreasingSubsequence(arr) {
const res = [arr[0]];
for (let i = 0; i < arr.length; ++i) {
if (res[res.length - 1] < arr[i]) {
res.push(arr[i]);
} else {
const index = res.findIndex((item) => item >= arr[i]);
if (index !== -1) {
res[index] = arr[i];
}
}
}
return res.length;
}
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const n = parseInt(readLine(), 10);
let arr = [];
for (let i = 0; i < n; i++) {
const arrItem = parseInt(readLine(), 10);
arr.push(arrItem);
}
let result = longestIncreasingSubsequence(arr);
ws.write(result + "\n");
ws.end();
}The Longest Increasing Subsequence Python Solution
from math import ceil
def calc_LIS(X):
P = [0 for _ in range(len(X))]
M = [0 for _ in range(len(X)+1)]
L = 0
for i in range(len(X)):
lo = 1
hi = L
while lo <= hi:
mid = int(ceil((lo+hi)/2))
if X[M[mid]] < X[i]:
lo = mid+1
else:
hi = mid-1
newL = lo
P[i] = M[newL-1]
M[newL] = i
if newL > L:
L = newL
S = [0 for _ in range(L)]
k = M[L]
for i in range(L-1, -1, -1):
S[i] = X[k]
k = P[k]
return S
X = []
n = int(input())
for i in range(n):
X.append(int(input()))
print(len(calc_LIS(X)))
