HackerRank The Longest Increasing Subsequence

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

Sample Output 0

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.

HackerRank The Longest Increasing Subsequence Game Problem Solution

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

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python