# Efficiently find length of longest Increasing Subsequence

Here given code implementation process.

``````// C Program
// Efficiently Find longest Increasing Subsequence
#include <stdio.h>

// Print the elements of given array
void printElement(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
printf("  %d", arr[i]);
}
}
void longestSubsequences(int arr[], int n)
{
if (n <= 0)
{
return;
}
int length = 1;
int mid = 0;
int low = 0;
int high = 0;
// Auxiliary array
int tail[n];
// Set intial value
for (int i = 0; i < n; ++i)
{
tail[i] = 0;
}
for (int i = 0; i < n; ++i)
{
if (arr[i] < arr[tail])
{
tail = i;
}
else if (arr[i] > arr[tail[length - 1]])
{
tail[length] = i;
length++;
}
else
{
low = -1;
high = length - 1;
// Find element position in tail array
while (high - low > 1)
{
mid = low + (high - low) / 2;
if (arr[tail[mid]] >= arr[i])
{
high = mid;
}
else
{
low = mid;
}
}
// Set new position
tail[high] = i;
}
}
printf("\n Array : ");
// Display given array
printElement(arr, n);
// Display calculated length
printf("\n Length  : %d\n ", length);
}
int main(int argc, char
const *argv[])
{
// Define array of integer elements
int arr1[] = {
8 , 4 , 7 , 5 , 1 , 9 , 3
};
int arr2[] = {
9 , 10 , 3 , 4 , 8 , 7 , 10
};
// Test Case A
// [ 8 , 4 , 7 , 5 , 1 , 9, 3]
// length of Longest increasing subsequence 3
// (4, 5, 9)
//  Result = 3
int n = sizeof(arr1) / sizeof(arr1);
longestSubsequences(arr1, n);
// Test Case B
// [ 9, 10, 3, 4, 8, 7, 10]
// length of Longest increasing subsequence 4
// (3, 4, 8, 10), (3, 4, 7, 10)
//  Result = 4
n = sizeof(arr2) / sizeof(arr2);
longestSubsequences(arr2, n);
return 0;
}``````

#### Output

`````` Array :   8  4  7  5  1  9  3
Length  : 3

Array :   9  10  3  4  8  7  10
Length  : 4
``````
``````// Java program for
// Efficiently find length of longest Increasing Subsequence
public class Subsequence
{
// Print the elements of given array
public void printElement(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
System.out.print(" " + arr[i]);
}
}
public void longestSubsequences(int[] arr, int n)
{
if (n <= 0)
{
return;
}
int length = 1;
int mid = 0;
int low = 0;
int high = 0;
// Auxiliary array
int[] tail = new int[n];
// Set intial value
for (int i = 0; i < n; ++i)
{
tail[i] = 0;
}
for (int i = 0; i < n; ++i)
{
if (arr[i] < arr[tail])
{
tail = i;
}
else if (arr[i] > arr[tail[length - 1]])
{
tail[length] = i;
length++;
}
else
{
low = -1;
high = length - 1;
// Find element position in tail array
while (high - low > 1)
{
mid = low + (high - low) / 2;
if (arr[tail[mid]] >= arr[i])
{
high = mid;
}
else
{
low = mid;
}
}
// Set new position
tail[high] = i;
}
}
System.out.print("\n Array : ");
// Display given array
printElement(arr, n);
System.out.print("\n Length : " + length + "\n ");
}
public static void main(String[] args)
{
// Define array of integer elements
int[] arr1 = {
8 , 4 , 7 , 5 , 1 , 9 , 3
};
int[] arr2 = {
9 , 10 , 3 , 4 , 8 , 7 , 10
};
// Test Case A
// [ 8 , 4 , 7 , 5 , 1 , 9, 3]
// length of Longest increasing subsequence 3
// (4, 5, 9)
//  Result = 3
int n = arr1.length;
// Test Case B
// [ 9, 10, 3, 4, 8, 7, 10]
// length of Longest increasing subsequence 4
// (3, 4, 8, 10), (3, 4, 7, 10)
//  Result = 4
n = arr2.length;
}
}``````

#### Output

`````` Array :  8 4 7 5 1 9 3
Length : 3

Array :  9 10 3 4 8 7 10
Length : 4
``````
``````// Include header file
#include <iostream>

using namespace std;
// C++ program for
// Efficiently find length of longest Increasing Subsequence
class Subsequence
{
public:
// Print the elements of given array
void printElement(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
cout << " " << arr[i];
}
}
void longestSubsequences(int arr[], int n)
{
if (n <= 0)
{
return;
}
int length = 1;
int mid = 0;
int low = 0;
int high = 0;
// Auxiliary array
int tail[n];
// Set intial value
for (int i = 0; i < n; ++i)
{
tail[i] = 0;
}
for (int i = 0; i < n; ++i)
{
if (arr[i] < arr[tail])
{
tail = i;
}
else if (arr[i] > arr[tail[length - 1]])
{
tail[length] = i;
length++;
}
else
{
low = -1;
high = length - 1;
// Find element position in tail array
while (high - low > 1)
{
mid = low + (high - low) / 2;
if (arr[tail[mid]] >= arr[i])
{
high = mid;
}
else
{
low = mid;
}
}
// Set new position
tail[high] = i;
}
}
cout << "\n Array : ";
// Display given array
this->printElement(arr, n);
cout << "\n Length : " << length << "\n ";
}
};
int main()
{
// Define array of integer elements
int arr1[] = {
8 , 4 , 7 , 5 , 1 , 9 , 3
};
int arr2[] = {
9 , 10 , 3 , 4 , 8 , 7 , 10
};
// Test Case A
// [ 8 , 4 , 7 , 5 , 1 , 9, 3]
// length of Longest increasing subsequence 3
// (4, 5, 9)
//  Result = 3
int n = sizeof(arr1) / sizeof(arr1);
// Test Case B
// [ 9, 10, 3, 4, 8, 7, 10]
// length of Longest increasing subsequence 4
// (3, 4, 8, 10), (3, 4, 7, 10)
//  Result = 4
n = sizeof(arr2) / sizeof(arr2);
return 0;
}``````

#### Output

`````` Array :  8 4 7 5 1 9 3
Length : 3

Array :  9 10 3 4 8 7 10
Length : 4
``````
``````// Include namespace system
using System;
// Csharp program for
// Efficiently find length of longest Increasing Subsequence
public class Subsequence
{
// Print the elements of given array
public void printElement(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
Console.Write(" " + arr[i]);
}
}
public void longestSubsequences(int[] arr, int n)
{
if (n <= 0)
{
return;
}
int length = 1;
int mid = 0;
int low = 0;
int high = 0;
// Auxiliary array
int[] tail = new int[n];
// Set intial value
for (int i = 0; i < n; ++i)
{
tail[i] = 0;
}
for (int i = 0; i < n; ++i)
{
if (arr[i] < arr[tail])
{
tail = i;
}
else if (arr[i] > arr[tail[length - 1]])
{
tail[length] = i;
length++;
}
else
{
low = -1;
high = length - 1;
// Find element position in tail array
while (high - low > 1)
{
mid = low + (high - low) / 2;
if (arr[tail[mid]] >= arr[i])
{
high = mid;
}
else
{
low = mid;
}
}
// Set new position
tail[high] = i;
}
}
Console.Write("\n Array : ");
// Display given array
this.printElement(arr, n);
Console.Write("\n Length : " + length + "\n ");
}
public static void Main(String[] args)
{
// Define array of integer elements
int[] arr1 = {
8 , 4 , 7 , 5 , 1 , 9 , 3
};
int[] arr2 = {
9 , 10 , 3 , 4 , 8 , 7 , 10
};
// Test Case A
// [ 8 , 4 , 7 , 5 , 1 , 9, 3]
// length of Longest increasing subsequence 3
// (4, 5, 9)
//  Result = 3
int n = arr1.Length;
// Test Case B
// [ 9, 10, 3, 4, 8, 7, 10]
// length of Longest increasing subsequence 4
// (3, 4, 8, 10), (3, 4, 7, 10)
//  Result = 4
n = arr2.Length;
}
}``````

#### Output

`````` Array :  8 4 7 5 1 9 3
Length : 3

Array :  9 10 3 4 8 7 10
Length : 4
``````
``````package main
import "fmt"
// Go program for
// Efficiently find length of longest Increasing Subsequence
type Subsequence struct {}
func getSubsequence() * Subsequence {
var me *Subsequence = &Subsequence {}
return me
}
// Print the elements of given array
func(this Subsequence) printElement(arr[] int, n int) {
for i := 0 ; i < n ; i++ {
fmt.Print(" ", arr[i])
}
}
func(this Subsequence) longestSubsequences(arr[] int, n int) {
if n <= 0 {
return
}
var length int = 1
var mid int = 0
var low int = 0
var high int = 0
// Auxiliary array
var tail = make([] int, n)
// Set intial value
for i := 0 ; i < n ; i++ {
tail[i] = 0
}
for i := 0 ; i < n ; i++ {
if arr[i] < arr[tail] {
tail = i
} else if arr[i] > arr[tail[length - 1]] {
tail[length] = i
length++
} else {
low = -1
high = length - 1
// Find element position in tail array
for (high - low > 1) {
mid = low + (high - low) / 2
if arr[tail[mid]] >= arr[i] {
high = mid
} else {
low = mid
}
}
// Set new position
tail[high] = i
}
}
fmt.Print("\n Array : ")
// Display given array
this.printElement(arr, n)
fmt.Print("\n Length : ", length, "\n ")
}
func main() {
var task * Subsequence = getSubsequence()
// Define array of integer elements
var arr1 = [] int {
8,
4,
7,
5,
1,
9,
3,
}
var arr2 = [] int {
9,
10,
3,
4,
8,
7,
10,
}
// Test Case A
// [ 8 , 4 , 7 , 5 , 1 , 9, 3]
// length of Longest increasing subsequence 3
// (4, 5, 9)
//  Result = 3
var n int = len(arr1)
// Test Case B
// [ 9, 10, 3, 4, 8, 7, 10]
// length of Longest increasing subsequence 4
// (3, 4, 8, 10), (3, 4, 7, 10)
//  Result = 4
n = len(arr2)
}``````

#### Output

`````` Array :  8 4 7 5 1 9 3
Length : 3

Array :  9 10 3 4 8 7 10
Length : 4
``````
``````<?php
// Php program for
// Efficiently find length of longest Increasing Subsequence
class Subsequence
{
// Print the elements of given array
public	function printElement(\$arr, \$n)
{
for (\$i = 0; \$i < \$n; ++\$i)
{
echo(" ".\$arr[\$i]);
}
}
public	function longestSubsequences(\$arr, \$n)
{
if (\$n <= 0)
{
return;
}
\$length = 1;
\$mid = 0;
\$low = 0;
\$high = 0;
// Auxiliary array
// Set intial value
\$tail = array_fill(0, \$n, 0);
for (\$i = 0; \$i < \$n; ++\$i)
{
if (\$arr[\$i] < \$arr[\$tail])
{
\$tail = \$i;
}
else if (\$arr[\$i] > \$arr[\$tail[\$length - 1]])
{
\$tail[\$length] = \$i;
\$length++;
}
else
{
\$low = -1;
\$high = \$length - 1;
// Find element position in tail array
while (\$high - \$low > 1)
{
\$mid = \$low + (int)((\$high - \$low) / 2);
if (\$arr[\$tail[\$mid]] >= \$arr[\$i])
{
\$high = \$mid;
}
else
{
\$low = \$mid;
}
}
// Set new position
\$tail[\$high] = \$i;
}
}
echo("\n Array : ");
// Display given array
\$this->printElement(\$arr, \$n);
echo("\n Length : ".\$length."\n ");
}
}

function main()
{
// Define array of integer elements
\$arr1 = array(8, 4, 7, 5, 1, 9, 3);
\$arr2 = array(9, 10, 3, 4, 8, 7, 10);
// Test Case A
// [ 8 , 4 , 7 , 5 , 1 , 9, 3]
// length of Longest increasing subsequence 3
// (4, 5, 9)
//  Result = 3
\$n = count(\$arr1);
// Test Case B
// [ 9, 10, 3, 4, 8, 7, 10]
// length of Longest increasing subsequence 4
// (3, 4, 8, 10), (3, 4, 7, 10)
//  Result = 4
\$n = count(\$arr2);
}
main();``````

#### Output

`````` Array :  8 4 7 5 1 9 3
Length : 3

Array :  9 10 3 4 8 7 10
Length : 4
``````
``````// Node JS program for
// Efficiently find length of longest Increasing Subsequence
class Subsequence
{
// Print the elements of given array
printElement(arr, n)
{
for (var i = 0; i < n; ++i)
{
process.stdout.write(" " + arr[i]);
}
}
longestSubsequences(arr, n)
{
if (n <= 0)
{
return;
}
var length = 1;
var mid = 0;
var low = 0;
var high = 0;
// Auxiliary array
// Set intial value
var tail = Array(n).fill(0);
for (var i = 0; i < n; ++i)
{
if (arr[i] < arr[tail])
{
tail = i;
}
else if (arr[i] > arr[tail[length - 1]])
{
tail[length] = i;
length++;
}
else
{
low = -1;
high = length - 1;
// Find element position in tail array
while (high - low > 1)
{
mid = low + parseInt((high - low) / 2);
if (arr[tail[mid]] >= arr[i])
{
high = mid;
}
else
{
low = mid;
}
}
// Set new position
tail[high] = i;
}
}
process.stdout.write("\n Array : ");
// Display given array
this.printElement(arr, n);
process.stdout.write("\n Length : " + length + "\n ");
}
}

function main()
{
// Define array of integer elements
var arr1 = [8, 4, 7, 5, 1, 9, 3];
var arr2 = [9, 10, 3, 4, 8, 7, 10];
// Test Case A
// [ 8 , 4 , 7 , 5 , 1 , 9, 3]
// length of Longest increasing subsequence 3
// (4, 5, 9)
//  Result = 3
var n = arr1.length;
// Test Case B
// [ 9, 10, 3, 4, 8, 7, 10]
// length of Longest increasing subsequence 4
// (3, 4, 8, 10), (3, 4, 7, 10)
//  Result = 4
n = arr2.length;
}
main();``````

#### Output

`````` Array :  8 4 7 5 1 9 3
Length : 3

Array :  9 10 3 4 8 7 10
Length : 4
``````
``````#  Python 3 program for
#  Efficiently find length of longest Increasing Subsequence
class Subsequence :
#  Print the elements of given list
def printElement(self, arr, n) :
i = 0
while (i < n) :
print(" ", arr[i], end = "")
i += 1

def longestSubsequences(self, arr, n) :
if (n <= 0) :
return

length = 1
mid = 0
low = 0
high = 0
#  Auxiliary list
#  Set intial value
tail =  * (n)
i = 0
while (i < n) :
if (arr[i] < arr[tail]) :
tail = i
elif (arr[i] > arr[tail[length - 1]]) :
tail[length] = i
length += 1
else :
low = -1
high = length - 1
#  Find element position in tail list
while (high - low > 1) :
mid = low + int((high - low) / 2)
if (arr[tail[mid]] >= arr[i]) :
high = mid
else :
low = mid

#  Set new position
tail[high] = i

i += 1

print("\n Array : ", end = "")
#  Display given list
self.printElement(arr, n)
print("\n Length : ", length ,"\n ", end = "")

def main() :
#  Define list of integer elements
arr1 = [8, 4, 7, 5, 1, 9, 3]
arr2 = [9, 10, 3, 4, 8, 7, 10]
#  Test Case A
#  [ 8 , 4 , 7 , 5 , 1 , 9, 3]
#  length of Longest increasing subsequence 3
#  (4, 5, 9)
#   Result = 3
n = len(arr1)
#  Test Case B
#  [ 9, 10, 3, 4, 8, 7, 10]
#  length of Longest increasing subsequence 4
#  (3, 4, 8, 10), (3, 4, 7, 10)
#   Result = 4
n = len(arr2)

if __name__ == "__main__": main()``````

#### Output

`````` Array :   8  4  7  5  1  9  3
Length :  3

Array :   9  10  3  4  8  7  10
Length :  4
``````
``````#  Ruby program for
#  Efficiently find length of longest Increasing Subsequence
class Subsequence
#  Print the elements of given array
def printElement(arr, n)
i = 0
while (i < n)
print(" ", arr[i])
i += 1
end

end

def longestSubsequences(arr, n)
if (n <= 0)
return
end

length = 1
mid = 0
low = 0
high = 0
#  Auxiliary array
#  Set intial value
tail = Array.new(n) {0}
i = 0
while (i < n)
if (arr[i] < arr[tail])
tail = i
elsif (arr[i] > arr[tail[length - 1]])
tail[length] = i
length += 1
else

low = -1
high = length - 1
#  Find element position in tail array
while (high - low > 1)
mid = low + (high - low) / 2
if (arr[tail[mid]] >= arr[i])
high = mid
else

low = mid
end

end

#  Set new position
tail[high] = i
end

i += 1
end

print("\n Array : ")
#  Display given array
self.printElement(arr, n)
print("\n Length : ", length ,"\n ")
end

end

def main()
#  Define array of integer elements
arr1 = [8, 4, 7, 5, 1, 9, 3]
arr2 = [9, 10, 3, 4, 8, 7, 10]
#  Test Case A
#  [ 8 , 4 , 7 , 5 , 1 , 9, 3]
#  length of Longest increasing subsequence 3
#  (4, 5, 9)
#   Result = 3
n = arr1.length
#  Test Case B
#  [ 9, 10, 3, 4, 8, 7, 10]
#  length of Longest increasing subsequence 4
#  (3, 4, 8, 10), (3, 4, 7, 10)
#   Result = 4
n = arr2.length
end

main()``````

#### Output

`````` Array :  8 4 7 5 1 9 3
Length : 3

Array :  9 10 3 4 8 7 10
Length : 4
``````
``````// Scala program for
// Efficiently find length of longest Increasing Subsequence
class Subsequence()
{
// Print the elements of given array
def printElement(arr: Array[Int], n: Int): Unit = {
var i: Int = 0;
while (i < n)
{
print(" " + arr(i));
i += 1;
}
}
def longestSubsequences(arr: Array[Int], n: Int): Unit = {
if (n <= 0)
{
return;
}
var length: Int = 1;
var mid: Int = 0;
var low: Int = 0;
var high: Int = 0;
// Auxiliary array
// Set intial value
var tail: Array[Int] = Array.fill[Int](n)(0);
var i: Int = 0;
while (i < n)
{
if (arr(i) < arr(tail(0)))
{
tail(0) = i;
}
else if (arr(i) > arr(tail(length - 1)))
{
tail(length) = i;
length += 1;
}
else
{
low = -1;
high = length - 1;
// Find element position in tail array
while (high - low > 1)
{
mid = low + (high - low) / 2;
if (arr(tail(mid)) >= arr(i))
{
high = mid;
}
else
{
low = mid;
}
}
// Set new position
tail(high) = i;
}
i += 1;
}
print("\n Array : ");
// Display given array
printElement(arr, n);
print("\n Length : " + length + "\n ");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Subsequence = new Subsequence();
// Define array of integer elements
var arr1: Array[Int] = Array(8, 4, 7, 5, 1, 9, 3);
var arr2: Array[Int] = Array(9, 10, 3, 4, 8, 7, 10);
// Test Case A
// [ 8 , 4 , 7 , 5 , 1 , 9, 3]
// length of Longest increasing subsequence 3
// (4, 5, 9)
//  Result = 3
var n: Int = arr1.length;
// Test Case B
// [ 9, 10, 3, 4, 8, 7, 10]
// length of Longest increasing subsequence 4
// (3, 4, 8, 10), (3, 4, 7, 10)
//  Result = 4
n = arr2.length;
}
}``````

#### Output

`````` Array :  8 4 7 5 1 9 3
Length : 3

Array :  9 10 3 4 8 7 10
Length : 4
``````
``````import Foundation;
// Swift 4 program for
// Efficiently find length of longest Increasing Subsequence
class Subsequence
{
// Print the elements of given array
func printElement(_ arr: [Int], _ n: Int)
{
var i: Int = 0;
while (i < n)
{
print(" ", arr[i], terminator: "");
i += 1;
}
}
func longestSubsequences(_ arr: [Int], _ n: Int)
{
if (n <= 0)
{
return;
}
var length: Int = 1;
var mid: Int = 0;
var low: Int = 0;
var high: Int = 0;
// Auxiliary array
// Set intial value
var tail: [Int] = Array(repeating: 0, count: n);
var i: Int = 0;
while (i < n)
{
if (arr[i] < arr[tail])
{
tail = i;
}
else if (arr[i] > arr[tail[length - 1]])
{
tail[length] = i;
length += 1;
}
else
{
low = -1;
high = length - 1;
// Find element position in tail array
while (high - low > 1)
{
mid = low + (high - low) / 2;
if (arr[tail[mid]] >= arr[i])
{
high = mid;
}
else
{
low = mid;
}
}
// Set new position
tail[high] = i;
}
i += 1;
}
print("\n Array : ", terminator: "");
// Display given array
self.printElement(arr, n);
print("\n Length : ", length ,"\n ", terminator: "");
}
}
func main()
{
// Define array of integer elements
let arr1: [Int] = [8, 4, 7, 5, 1, 9, 3];
let arr2: [Int] = [9, 10, 3, 4, 8, 7, 10];
// Test Case A
// [ 8 , 4 , 7 , 5 , 1 , 9, 3]
// length of Longest increasing subsequence 3
// (4, 5, 9)
//  Result = 3
var n: Int = arr1.count;
// Test Case B
// [ 9, 10, 3, 4, 8, 7, 10]
// length of Longest increasing subsequence 4
// (3, 4, 8, 10), (3, 4, 7, 10)
//  Result = 4
n = arr2.count;
}
main();``````

#### Output

`````` Array :   8  4  7  5  1  9  3
Length :  3

Array :   9  10  3  4  8  7  10
Length :  4
``````
``````// Kotlin program for
// Efficiently find length of longest Increasing Subsequence
class Subsequence
{
// Print the elements of given array
fun printElement(arr: Array < Int > , n: Int): Unit
{
var i: Int = 0;
while (i < n)
{
print(" " + arr[i]);
i += 1;
}
}
fun longestSubsequences(arr: Array < Int > , n: Int): Unit
{
if (n <= 0)
{
return;
}
var length: Int = 1;
var mid: Int;
var low: Int;
var high: Int ;
// Auxiliary array
// Set intial value
val tail: Array < Int > = Array(n)
{
0
};
var i: Int = 0;
while (i < n)
{
if (arr[i] < arr[tail])
{
tail = i;
}
else if (arr[i] > arr[tail[length - 1]])
{
tail[length] = i;
length += 1;
}
else
{
low = -1;
high = length - 1;
// Find element position in tail array
while (high - low > 1)
{
mid = low + (high - low) / 2;
if (arr[tail[mid]] >= arr[i])
{
high = mid;
}
else
{
low = mid;
}
}
// Set new position
tail[high] = i;
}
i += 1;
}
print("\n Array : ");
// Display given array
this.printElement(arr, n);
print("\n Length : " + length + "\n ");
}
}
fun main(args: Array < String > ): Unit
{
// Define array of integer elements
val arr1: Array < Int > = arrayOf(8, 4, 7, 5, 1, 9, 3);
val arr2: Array < Int > = arrayOf(9, 10, 3, 4, 8, 7, 10);
// Test Case A
// [ 8 , 4 , 7 , 5 , 1 , 9, 3]
// length of Longest increasing subsequence 3
// (4, 5, 9)
//  Result = 3
var n: Int = arr1.count();
// Test Case B
// [ 9, 10, 3, 4, 8, 7, 10]
// length of Longest increasing subsequence 4
// (3, 4, 8, 10), (3, 4, 7, 10)
//  Result = 4
n = arr2.count();
}``````

#### Output

`````` Array :  8 4 7 5 1 9 3
Length : 3

Array :  9 10 3 4 8 7 10
Length : 4
``````

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

### New Comment 