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