Length of longest increasing subsequence
The length of the longest increasing subsequence is a problem in computer science and mathematics that involves finding the length of the longest subsequence of a given sequence in which the elements are in increasing order. This subsequence does not have to be contiguous, meaning that the elements are not required to appear consecutively in the original sequence. The problem can be solved using dynamic programming techniques.
Problem Statement:
Given a sequence of numbers, we need to find the length of the longest increasing subsequence and also print the subsequence itself. An increasing subsequence is defined as a subsequence in which the elements are arranged in increasing order.
// C Program
// Length of 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;
}
// Define auxiliary array
int length[n];
// Define some auxiliary variables
int i = 0;
int j = 0;
int result = 1;
// Set the initial value in auxiliary array
for (i = 0; i < n; i++)
{
length[i] = 1;
}
// Execute loop through by size of arr
for (i = 0; i < n; i++)
{
// calculate increasing subsequence length
for (j = 0; j < i; j++)
{
if (arr[i] > arr[j])
{
if (length[j] + 1 > length[i])
{
length[i] = length[j] + 1;
if (length[i] > result)
{
result = length[i];
}
}
}
}
}
// Display given array
printElement(arr, n);
// Display calculated result
printf("\n Length of Longest increasing subsequence is : %d\n", result);
}
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
8 4 7 5 1 9 3
Length of Longest increasing subsequence is : 3
9 10 3 4 8 7 10
Length of Longest increasing subsequence is : 4// Java program for
// 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;
}
// Define auxiliary array
int[] length = new int[n];
// Define some auxiliary variables
int i = 0;
int j = 0;
int result = 1;
// Set the initial value in auxiliary array
for (i = 0; i < n; i++)
{
length[i] = 1;
}
// Execute loop through by size of arr
for (i = 0; i < n; i++)
{
// calculate increasing subsequence length
for (j = 0; j < i; j++)
{
if (arr[i] > arr[j])
{
if (length[j] + 1 > length[i])
{
length[i] = length[j] + 1;
if (length[i] > result)
{
result = length[i];
}
}
}
}
}
// Display given array
printElement(arr, n);
// Display calculated result
System.out.print("\n Length of Longest increasing subsequence is : " +
result + "\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
8 4 7 5 1 9 3
Length of Longest increasing subsequence is : 3
9 10 3 4 8 7 10
Length of Longest increasing subsequence is : 4// Include header file
#include <iostream>
using namespace std;
// C++ program for
// 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;
}
// Define auxiliary array
int length[n];
// Define some auxiliary variables
int i = 0;
int j = 0;
int result = 1;
// Set the initial value in auxiliary array
for (i = 0; i < n; i++)
{
length[i] = 1;
}
// Execute loop through by size of arr
for (i = 0; i < n; i++)
{
// calculate increasing subsequence length
for (j = 0; j < i; j++)
{
if (arr[i] > arr[j])
{
if (length[j] + 1 > length[i])
{
length[i] = length[j] + 1;
if (length[i] > result)
{
result = length[i];
}
}
}
}
}
// Display given array
this->printElement(arr, n);
// Display calculated result
cout << "\n Length of Longest increasing subsequence is : "
<< result
<< "\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
8 4 7 5 1 9 3
Length of Longest increasing subsequence is : 3
9 10 3 4 8 7 10
Length of Longest increasing subsequence is : 4// Include namespace system
using System;
// Csharp program for
// 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;
}
// Define auxiliary array
int[] length = new int[n];
// Define some auxiliary variables
int i = 0;
int j = 0;
int result = 1;
// Set the initial value in auxiliary array
for (i = 0; i < n; i++)
{
length[i] = 1;
}
// Execute loop through by size of arr
for (i = 0; i < n; i++)
{
// calculate increasing subsequence length
for (j = 0; j < i; j++)
{
if (arr[i] > arr[j])
{
if (length[j] + 1 > length[i])
{
length[i] = length[j] + 1;
if (length[i] > result)
{
result = length[i];
}
}
}
}
}
// Display given array
this.printElement(arr, n);
// Display calculated result
Console.Write("\n Length of Longest increasing subsequence is : " +
result + "\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
8 4 7 5 1 9 3
Length of Longest increasing subsequence is : 3
9 10 3 4 8 7 10
Length of Longest increasing subsequence is : 4package main
import "fmt"
// Go program for
// 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
}
// Define auxiliary array
var length = make([] int, n)
// Set initial 1 length of each element
for i := 0; i < n; i++ {
length[i] = 1
}
// Define some auxiliary variables
var i int = 0
var j int = 0
var result int = 1
// Execute loop through by size of arr
for i = 0 ; i < n ; i++ {
// calculate increasing subsequence length
for j = 0 ; j < i ; j++ {
if arr[i] > arr[j] {
if length[j] + 1 > length[i] {
length[i] = length[j] + 1
if length[i] > result {
result = length[i]
}
}
}
}
}
// Display given array
this.printElement(arr, n)
// Display calculated result
fmt.Println("\n Length of Longest increasing subsequence is : ",
result)
}
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
8 4 7 5 1 9 3
Length of Longest increasing subsequence is : 3
9 10 3 4 8 7 10
Length of Longest increasing subsequence is : 4<?php
// Php program for
// 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;
}
// Define auxiliary array
// Set initial 1 length of each element
$length = array_fill(0, $n, 1);
// Define some auxiliary variables
$i = 0;
$j = 0;
$result = 1;
// Execute loop through by size of arr
for ($i = 0; $i < $n; $i++)
{
// calculate increasing subsequence length
for ($j = 0; $j < $i; $j++)
{
if ($arr[$i] > $arr[$j])
{
if ($length[$j] + 1 > $length[$i])
{
$length[$i] = $length[$j] + 1;
if ($length[$i] > $result)
{
$result = $length[$i];
}
}
}
}
}
// Display given array
$this->printElement($arr, $n);
// Display calculated result
echo("\n Length of Longest increasing subsequence is : ".$result.
"\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
8 4 7 5 1 9 3
Length of Longest increasing subsequence is : 3
9 10 3 4 8 7 10
Length of Longest increasing subsequence is : 4// Node JS program for
// 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;
}
// Define auxiliary array
// Set initial 1 length of each element
var length = Array(n).fill(1);
// Define some auxiliary variables
var i = 0;
var j = 0;
var result = 1;
// Execute loop through by size of arr
for (i = 0; i < n; i++)
{
// calculate increasing subsequence length
for (j = 0; j < i; j++)
{
if (arr[i] > arr[j])
{
if (length[j] + 1 > length[i])
{
length[i] = length[j] + 1;
if (length[i] > result)
{
result = length[i];
}
}
}
}
}
// Display given array
this.printElement(arr, n);
// Display calculated result
console.log("\n Length of Longest increasing subsequence is : " +
result );
}
}
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
8 4 7 5 1 9 3
Length of Longest increasing subsequence is : 3
9 10 3 4 8 7 10
Length of Longest increasing subsequence is : 4# Python 3 program for
# 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
# Define auxiliary list
# Set initial 1 length of each element
length = [1] * (n)
# Define some auxiliary variables
i = 0
j = 0
result = 1
i = 0
# Execute loop through by size of arr
while (i < n) :
j = 0
# calculate increasing subsequence length
while (j < i) :
if (arr[i] > arr[j]) :
if (length[j] + 1 > length[i]) :
length[i] = length[j] + 1
if (length[i] > result) :
result = length[i]
j += 1
i += 1
# Display given list
self.printElement(arr, n)
# Display calculated result
print("\n Length of Longest increasing subsequence is : ", result)
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
8 4 7 5 1 9 3
Length of Longest increasing subsequence is : 3
9 10 3 4 8 7 10
Length of Longest increasing subsequence is : 4# Ruby program for
# 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
# Define auxiliary array
# Set initial 1 length of each element
length = Array.new(n) {1}
# Define some auxiliary variables
i = 0
j = 0
result = 1
i = 0
# Execute loop through by size of arr
while (i < n)
j = 0
# calculate increasing subsequence length
while (j < i)
if (arr[i] > arr[j])
if (length[j] + 1 > length[i])
length[i] = length[j] + 1
if (length[i] > result)
result = length[i]
end
end
end
j += 1
end
i += 1
end
# Display given array
self.printElement(arr, n)
# Display calculated result
print("\n Length of Longest increasing subsequence is : ",
result, "\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
8 4 7 5 1 9 3
Length of Longest increasing subsequence is : 3
9 10 3 4 8 7 10
Length of Longest increasing subsequence is : 4
import Foundation;
// Swift 4 program for
// 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;
}
// Define auxiliary array
// Set initial 1 length of each element
var length: [Int] = Array(repeating: 1, count: n);
// Define some auxiliary variables
var i: Int = 0;
var j: Int = 0;
var result: Int = 1;
// Execute loop through by size of arr
while (i < n)
{
j = 0;
// calculate increasing subsequence length
while (j < i)
{
if (arr[i] > arr[j])
{
if (length[j] + 1 > length[i])
{
length[i] = length[j] + 1;
if (length[i] > result)
{
result = length[i];
}
}
}
j += 1;
}
i += 1;
}
// Display given array
self.printElement(arr, n);
// Display calculated result
print("\n Length of Longest increasing subsequence is : ",
result);
}
}
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
8 4 7 5 1 9 3
Length of Longest increasing subsequence is : 3
9 10 3 4 8 7 10
Length of Longest increasing subsequence is : 4// Scala program for
// 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;
}
// Define auxiliary array
// Set initial 1 length of each element
var length: Array[Int] = Array.fill[Int](n)(1);
// Define some auxiliary variables
var i: Int = 0;
var j: Int = 0;
var result: Int = 1;
// Execute loop through by size of arr
while (i < n)
{
j = 0;
// calculate increasing subsequence length
while (j < i)
{
if (arr(i) > arr(j))
{
if (length(j) + 1 > length(i))
{
length(i) = length(j) + 1;
if (length(i) > result)
{
result = length(i);
}
}
}
j += 1;
}
i += 1;
}
// Display given array
printElement(arr, n);
// Display calculated result
println("\n Length of Longest increasing subsequence is : " +
result);
}
}
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
8 4 7 5 1 9 3
Length of Longest increasing subsequence is : 3
9 10 3 4 8 7 10
Length of Longest increasing subsequence is : 4// Kotlin program for
// 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;
}
// Define auxiliary array
// Set initial 1 length of each element
var length: Array < Int > = Array(n)
{
1
};
// Define some auxiliary variables
var i: Int = 0;
var j: Int ;
var result: Int = 1;
// Execute loop through by size of arr
while (i < n)
{
j = 0;
// calculate increasing subsequence length
while (j < i)
{
if (arr[i] > arr[j])
{
if (length[j] + 1 > length[i])
{
length[i] = length[j] + 1;
if (length[i] > result)
{
result = length[i];
}
}
}
j += 1;
}
i += 1;
}
// Display given array
this.printElement(arr, n);
// Display calculated result
println("\n Length of Longest increasing subsequence is : " +
result);
}
}
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
8 4 7 5 1 9 3
Length of Longest increasing subsequence is : 3
9 10 3 4 8 7 10
Length of Longest increasing subsequence is : 4To solve this problem, we can use dynamic programming to find the length of the longest increasing subsequence.
We define an auxiliary array, length, to store the lengths of the increasing subsequences ending at
each position in the given array. We also initialize each element of length to 1 because every
element itself forms an increasing subsequence of length 1.
We then iterate through the given array and, for each element, compare it with all the previous elements. If we find a previous element that is smaller than the current element, we update the length of the increasing subsequence ending at the current position. We do this by checking if adding the current element to the subsequence ending at the previous element will result in a longer subsequence than what we already have.
We keep track of the maximum length encountered so far and update it whenever we find a longer subsequence. Finally, we print the elements of the given array and display the length of the longest increasing subsequence.
Let's walk through the code to understand it better:
-
The
printElementfunction is a helper function that prints the elements of an array. -
The
longestSubsequencesfunction takes an arrayarrand its lengthnas input and calculates the length of the longest increasing subsequence using dynamic programming. -
Inside the
longestSubsequencesfunction, we initialize variablesi,j, andresult. The variableiis used for iterating through the given array,jis used for comparing the current element with previous elements, andresultstores the length of the longest increasing subsequence. -
We create an auxiliary array
lengthof sizento store the lengths of the increasing subsequences ending at each position. -
We iterate through the given array and, for each element, we compare it with all the previous elements. If we find a previous element that is smaller, we update the length of the increasing subsequence ending at the current position.
-
We also keep track of the maximum length encountered so far and update
resultwhenever we find a longer subsequence. -
After the iteration, we call the
printElementfunction to print the elements of the given array. -
Finally, we print the length of the longest increasing subsequence stored in
result.
The code includes two test cases, arr1 and arr2, which are arrays with different
elements. We calculate the longest increasing subsequence for each test case and display the results.
Test Case A: [8, 4, 7, 5, 1, 9, 3] The longest increasing subsequence is [4, 5, 9] with a length of 3.
Test Case B: [9, 10, 3, 4, 8, 7, 10] The longest increasing subsequences are [3, 4, 8, 10] and [3, 4, 7, 10], both with a length of 4.
The problem of finding the length of the longest increasing subsequence is solved using dynamic programming techniques. The code iterates through the given array, compares each element with previous elements, and updates the length of the increasing subsequence ending at each position. By keeping track of the maximum length encountered, we can find the length of the longest increasing subsequence. This problem has various applications, such as in data analysis, sequence alignment, and optimization algorithms.
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