Table of Contents

# The Longest Increasing Subsequence – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

# Solutions of Algorithms Data Structures Hard HackerRank:

## Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts

# C++ The Longest Increasing Subsequence HackerRank Solution

#include <climits> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <map> #include <set> #include <queue> #include <string> #include <vector> #include <algorithm> #include <iostream> #include <sstream> #define io_r freopen("input.txt","r",stdin); #define io_w freopen("output.txt","w",stdout); #define io_file io_r; io_w; #define ll long long #define PB push_back #define MP make_pair #define f(i,a,b) for (int i = a; i<b; i++) #define rep(i,n) for (int i = 0; i<n; i++) #define clr(x, y) memset(x, y, sizeof x) #define MAX 1000100 #define INF INT_MAX/2 using namespace std; int v[MAX]; int pd[MAX], tailTable[MAX]; int CeilIndex(int A[], int l, int r, int key) { int m; while( r - l > 1 ) { m = l + (r - l)/2; (A[m] >= key ? r : l) = m; // ternary expression returns an l-value } return r; } int lis(int A[], int size) { int len; tailTable[0] = A[0]; len = 1; for( int i = 1; i < size; i++ ) { if( A[i] < tailTable[0] ) tailTable[0] = A[i]; else if( A[i] > tailTable[len-1] ) tailTable[len++] = A[i]; else tailTable[CeilIndex(tailTable, -1, len-1, A[i])] = A[i]; } return len; } int main (){ int n; scanf ("%d", &n); rep (i, n) scanf ("%d", &v[i]); printf ("%d\n", lis(v, n)); return 0; }

# Java The Longest Increasing Subsequence HackerRank Solution

import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; import java.io.BufferedReader; import java.io.File; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; public class Solution { FastScanner input; PrintWriter output; final int MAX_N = (int)(1e6+6); final int MAX_A = (int)(1e5+5); public static void main(String[] arg) { new Solution().run(); } void run() { try { boolean debug = false; //boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null; if (debug) input = new FastScanner(new File("longest_increasing_subsequent.in")); else input = new FastScanner(); output = new PrintWriter(System.out); solve(); output.close(); } catch (IOException e) { e.printStackTrace(); } } void solve() throws IOException { int n = input.nextInt(), res = 0; int f[] = new int[MAX_N]; Arrays.fill(f, -1); for (int i = 0; i < n; ++i) { int a = input.nextInt(); if (a > f[res]) f[++res] = a; else if (a < f[1]) f[1] = a; else { int l = 1, r = res-1, t = -1; while (l <= r) { int mid = (l+r)>>1; if (f[mid] < a) t = l = mid+1; else r = mid-1; } if (t > 0) f[t] = a; } } output.println(res); } } class FastScanner { BufferedReader br; StringTokenizer st; FastScanner(File f) { try { br = new BufferedReader(new FileReader(f)); } catch (FileNotFoundException e) { e.printStackTrace(); } } FastScanner() { br = new BufferedReader(new InputStreamReader(System.in)); } String next() { while (st == null || !st.hasMoreTokens()) { try { String line = br.readLine(); if (line == null) return null; st = new StringTokenizer(line); } catch (IOException e) { e.printStackTrace(); } } return st.nextToken(); } int nextInt() { return Integer.parseInt(next()); } long nextLong() { return Long.parseLong(next()); } double nextDouble() { return Double.parseDouble(next()); } } class Pair<T1 extends Comparable<T1>, T2 extends Comparable<T2>> implements Comparable<Pair<T1, T2>> { public T1 first; public T2 second; public Pair(T1 first, T2 second) { this.first = first; this.second = second; } public int compareTo(Pair<T1, T2> o) { if (first.compareTo(o.first) != 0) return first.compareTo(o.first); return second.compareTo(o.second); } }

# Python 3 The Longest Increasing Subsequence HackerRank Solution

def subsequence(seq): if not seq: return seq M = [None] * len(seq) # offset by 1 (j -> j-1) P = [None] * len(seq) # Since we have at least one element in our list, we can start by # knowing that the there's at least an increasing subsequence of length one: # the first element. L = 1 M[0] = 0 # Looping over the sequence starting from the second element for i in range(1, len(seq)): # Binary search: we want the largest j <= L # such that seq[M[j]] < seq[i] (default j = 0), # hence we want the lower bound at the end of the search process. lower = 0 upper = L # Since the binary search will not look at the upper bound value, # we'll have to check that manually if seq[M[upper-1]] < seq[i]: j = upper else: # actual binary search loop while upper - lower > 1: mid = (upper + lower) // 2 if seq[M[mid-1]] < seq[i]: lower = mid else: upper = mid j = lower # this will also set the default value to 0 P[i] = M[j-1] if j == L or seq[i] < seq[M[j]]: M[j] = i L = max(L, j+1) # Building the result: [seq[M[L-1]], seq[P[M[L-1]]], seq[P[P[M[L-1]]]], ...] result = [] pos = M[L-1] for _ in range(L): result.append(seq[pos]) pos = P[pos] return result[::-1] # reversing i=0 import sys seq = [] i=0 for line in sys.stdin: if i == 0: i+=1 else: seq.append(int(line.split()[0])) print (len(subsequence(seq)))

# Python 2 The Longest Increasing Subsequence HackerRank Solution

# Enter your code here. Read input from STDIN. Print output to STDOUT from bisect import bisect_left def LongestIncreasingSubsequence(S): head = [] tail = [None] for x in S: i = bisect_left(head,x) if i >= len(head): head.append(x) if i > 0: tail.append((head[i-1],tail[i-1])) elif head[i] > x: head[i] = x if i > 0: tail[i] = head[i-1],tail[i-1] if not head: return [] output = [head[-1]] pair = tail[-1] while pair: x,pair = pair output.append(x) output.reverse() return len(output) n = int(raw_input()) a = list() for i in range(n): temp = int(raw_input()) a.append(temp) print LongestIncreasingSubsequence(a)

# C The Longest Increasing Subsequence HackerRank Solution

#include <stdio.h> int n,a[1000000],b[1000000]; int getRight(int *Arr,int left,int right,int value) { int mid; while(right>left+1) { mid=left+(right-left)/2; if(Arr[mid]>=value)right=mid; else left=mid; } return right; } int CalcLIS() { int i,res=1; b[0]=a[0]; for(i=1;i<n;i++) { if(a[i]<b[0]) b[0]=a[i]; else if(a[i]>b[res-1]) b[res++]=a[i]; else b[getRight(b,-1,res-1,a[i])]=a[i]; } return res; } int main() { int i; scanf("%d",&n); for(i=0;i<n;i++)scanf("%d",&a[i]); printf("%d",CalcLIS()); return 0; }

## Warmup

Implementation

Strings

Sorting

Search

Graph Theory

Greedy

Dynamic Programming

Constructive Algorithms

Bit Manipulation

Recursion

Game Theory

NP Complete

Debugging

## Leave a comment below