Posted on by Kalkicode
Code Dynamic Programming

Efficiently find length of longest Increasing Subsequence

The problem of finding the length of the longest increasing subsequence in an array is a common task in computer science and algorithms. Given an array of integers, the goal is to determine the length of the longest subsequence where the elements are arranged in increasing order. In this article, we will discuss an efficient algorithm to solve this problem using dynamic programming.

Understanding the Problem:

Before diving into the solution, let's understand the problem statement with an example. Consider an array [8, 4, 7, 5, 1, 9, 3]. The longest increasing subsequence in this array is [4, 5, 9], and its length is 3. Similarly, for the array [9, 10, 3, 4, 8, 7, 10], the longest increasing subsequence has length 4, which can be [3, 4, 8, 10] or [3, 4, 7, 10].

Code Solution

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

Solution Approach:

To efficiently find the length of the longest increasing subsequence, we will use an algorithm based on dynamic programming. Let's walk through the steps of the algorithm:

  1. Initialize a variable 'length' to 1, which will hold the length of the longest increasing subsequence.
  2. Create an auxiliary array called 'tail' of size 'n', where 'n' is the number of elements in the given array. Initialize all elements of 'tail' to 0.
  3. Traverse the given array from left to right.
  4. For each element 'arr[i]' in the array, do the following:
    • If 'arr[i]' is less than the smallest element in 'tail', update 'tail[0]' with 'i'.
    • If 'arr[i]' is greater than the largest element in 'tail', increment 'length' by 1, update 'tail[length]' with 'i'.
    • If 'arr[i]' is neither the smallest nor the largest, find the correct position for 'arr[i]' in the 'tail' array using binary search.
      • Set 'low' to -1 and 'high' to 'length - 1'.
      • While 'high - low' is greater than 1, perform the following:
        • Calculate 'mid' as 'low + (high - low) / 2'.
        • If 'arr[tail[mid]]' is greater than or equal to 'arr[i]', set 'high' to 'mid'; otherwise, set 'low' to 'mid'.
      • Set 'tail[high]' to 'i'.
  5. After traversing the entire array, the 'length' variable will hold the length of the longest increasing subsequence.
  6. Output the length of the subsequence.

Explanation with Example:

Let's apply the above algorithm to the given arrays in the provided C code.

For Test Case A [8, 4, 7, 5, 1, 9, 3]:

  • Initialize 'length' to 1 and 'tail' as [0, 0, 0, 0, 0, 0, 0].
  • Traverse the array and update 'tail' accordingly:
    • For 8, update 'tail[0]' to 0.
    • For 4, update 'tail[0]' to 1.
    • For 7, update 'tail[0]' to 1.
    • For 5, update 'tail[0]' to 1.
    • For 1, update 'tail[0]' to 1.
    • For 9, update 'tail[1]' to 5 and increment 'length' to 2.
    • For 3, update 'tail[0]' to 1.
  • The length of the longest increasing subsequence is 3.

For Test Case B [9, 10, 3, 4, 8, 7, 10]:

  • Initialize 'length' to 1 and 'tail' as [0, 0, 0, 0, 0, 0, 0].
  • Traverse the array and update 'tail' accordingly:
    • For 9, update 'tail[0]' to 0.
    • For 10, update 'tail[1]' to 1 and increment 'length' to 2.
    • For 3, update 'tail[0]' to 0.
    • For 4, update 'tail[1]' to 3.
    • For 8, update 'tail[2]' to 4 and increment 'length' to 3.
    • For 7, update 'tail[2]' to 5.
    • For 10, update 'tail[3]' to 6 and increment 'length' to 4.
  • The length of the longest increasing subsequence is 4.

In this article, we have explored an efficient algorithm to find the length of the longest increasing subsequence in an array. By utilizing dynamic programming and binary search, we can solve this problem in an optimized manner. The algorithm has a time complexity of O(n log n), where n is the number of elements in the array. This approach is especially useful when dealing with large arrays and performance is crucial.

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