Skip to main content

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[0]])
		{
			tail[0] = 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[0]);
	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[0]);
	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[0]])
			{
				tail[0] = 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)
	{
		Subsequence task = new Subsequence();
		// 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;
		task.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 = arr2.length;
		task.longestSubsequences(arr2, n);
	}
}

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[0]])
			{
				tail[0] = 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()
{
	Subsequence *task = new Subsequence();
	// 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[0]);
	task->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[0]);
	task->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
// 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[0]])
			{
				tail[0] = 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)
	{
		Subsequence task = new Subsequence();
		// 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;
		task.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 = arr2.Length;
		task.longestSubsequences(arr2, n);
	}
}

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[0]] {
			tail[0] = 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)
	task.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 = len(arr2)
	task.longestSubsequences(arr2, n)
}

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[0]])
			{
				$tail[0] = $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()
{
	$task = new Subsequence();
	// 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);
	$task->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 = count($arr2);
	$task->longestSubsequences($arr2, $n);
}
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[0]])
			{
				tail[0] = 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()
{
	var task = new Subsequence();
	// 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;
	task.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 = arr2.length;
	task.longestSubsequences(arr2, n);
}
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 = [0] * (n)
		i = 0
		while (i < n) :
			if (arr[i] < arr[tail[0]]) :
				tail[0] = 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() :
	task = Subsequence()
	#  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)
	task.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 = len(arr2)
	task.longestSubsequences(arr2, n)

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[0]]) 
				tail[0] = 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() 
	task = Subsequence.new()
	#  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
	task.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 = arr2.length
	task.longestSubsequences(arr2, n)
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;
		task.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 = arr2.length;
		task.longestSubsequences(arr2, n);
	}
}

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[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 : ", terminator: "");
		// Display given array
		self.printElement(arr, n);
		print("\n Length : ", length ,"\n ", terminator: "");
	}
}
func main()
{
	let task: Subsequence = Subsequence();
	// 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;
	task.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 = arr2.count;
	task.longestSubsequences(arr2, n);
}
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[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
		this.printElement(arr, n);
		print("\n Length : " + length + "\n ");
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Subsequence = Subsequence();
	// 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();
	task.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 = arr2.count();
	task.longestSubsequences(arr2, n);
}

Output

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

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




Comment

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