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:
- Initialize a variable 'length' to 1, which will hold the length of the longest increasing subsequence.
- 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.
- Traverse the given array from left to right.
- 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'.
- After traversing the entire array, the 'length' variable will hold the length of the longest increasing subsequence.
- 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.
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