Count the number of longest increasing subsequence
In this article, we will discuss the problem of counting the number of longest increasing subsequences in an array. Given an array of integers, an increasing subsequence is a sequence of elements in which each element is larger than its previous element. The task is to find the length of the longest increasing subsequence and count the number of subsequences with that length.
Problem Statement
The problem can be stated as follows:
Given an array of integers, we need to find the length of the longest increasing subsequence and count the number of
subsequences with that length.
Pseudocode Algorithm
// Print the elements of given array
printElement(arr[], n)
for i = 0 to n-1
print arr[i]
// Calculates the all number of longest increasing subsequence
longestSubsequences(arr[], n)
if n <= 0
return
// Define two auxiliary arrays
length[n]
counter[n]
// Define some auxiliary variables
i = 0
j = 0
result = 0
max = 0
// Set the initial values in auxiliary arrays
for i = 0 to n-1
length[i] = 1
counter[i] = 1
// Execute loop through by size of arr
for i = 0 to n-1
// calculate increasing subsequence length and count their size
for j = 0 to i-1
if arr[i] > arr[j]
if length[j] + 1 > length[i]
counter[i] = counter[j]
length[i] = length[j] + 1
else if length[j] + 1 == length[i]
counter[i] += counter[j]
// Count the length of the longest subsequence
for i = 0 to n-1
if max < length[i]
max = length[i]
// Count the number of longest increasing subsequences with max length
for i = 0 to n-1
if length[i] == max
result += counter[i]
// Display given array
printElement(arr, n)
// Display calculated result
print "Result: " + result
// C program for
// Count the number 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]);
}
}
// Calculates the all number of longest increasing subsequence
void longestSubsequences(int arr[], int n)
{
if (n <= 0)
{
return;
}
// Define two auxiliary array
int length[n];
int counter[n];
// Define some auxiliary variables
int i = 0;
int j = 0;
int result = 0;
int max = 0;
// Set the initial value in auxiliary array
for (i = 0; i < n; i++)
{
length[i] = 1;
counter[i] = 1;
}
// Execute loop through by size of arr
for (i = 0; i < n; i++)
{
// calculate increasing subsequence length and count their size
for (j = 0; j < i; j++)
{
if (arr[i] > arr[j])
{
if (length[j] + 1 > length[i])
{
counter[i] = counter[j];
length[i] = length[j] + 1;
}
else if (length[j] + 1 == length[i])
{
counter[i] += counter[j];
}
}
}
}
// Count the length of longest subsequence
for (i = 0; i < n; i++)
{
if (max < length[i])
{
// When gets new largest subsequence
max = length[i];
}
}
// Count the number of longest increasing subsequence in max length
for (i = 0; i < n; i++)
{
if (length[i] == max)
{
// Add the repeated subsequence of max length
result += counter[i];
}
}
// Display given array
printElement(arr, n);
// Display calculated result
printf("\n Result : %d\n", result);
}
int main(int argc, char
const *argv[])
{
// Define array of integer elements
int arr1[] = {
8 , 4 , 7 , 5 , 1 , 3
};
int arr2[] = {
9 , 10 , 3 , 4 , 8 , 7 , 10
};
int arr3[] = {
7 , 6 , 5 , 1
};
// Test Case A
// [ 8, 4, 7, 5, 1, 3]
// length of Longest increasing subsequence 2
// (8,7), (4, 5), (1,3)
// 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 = 2
n = sizeof(arr2) / sizeof(arr2[0]);
longestSubsequences(arr2, n);
// Test Case C
// [ 7 , 6, 5]
// length of Longest increasing subsequence 1
// (7),(6),(5)
// Result = 4
n = sizeof(arr3) / sizeof(arr3[0]);
longestSubsequences(arr3, n);
return 0;
}input
8 4 7 5 1 3
Result : 3
9 10 3 4 8 7 10
Result : 2
7 6 5 1
Result : 4/*
Java Program
Count the number 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]);
}
}
// Calculates the all number of longest increasing subsequence
public void longestSubsequences(int[] arr, int n)
{
if (n <= 0)
{
return;
}
// Define two auxiliary array
int[] length = new int[n];
int[] counter = new int[n];
// Define some auxiliary variables
int i = 0;
int j = 0;
int result = 0;
int max = 0;
// Set the initial value in auxiliary array
for (i = 0; i < n; i++)
{
length[i] = 1;
counter[i] = 1;
}
// Execute loop through by size of arr
for (i = 0; i < n; i++)
{
// calculate increasing subsequence length and count their size
for (j = 0; j < i; j++)
{
if (arr[i] > arr[j])
{
if (length[j] + 1 > length[i])
{
counter[i] = counter[j];
length[i] = length[j] + 1;
}
else if (length[j] + 1 == length[i])
{
counter[i] += counter[j];
}
}
}
}
// Count the length of longest subsequence
for (i = 0; i < n; i++)
{
if (max < length[i])
{
// When gets new largest subsequence
max = length[i];
}
}
// Count the number of longest increasing subsequence in max length
for (i = 0; i < n; i++)
{
if (length[i] == max)
{
// Add the repeated subsequence of max length
result += counter[i];
}
}
// Display given array
printElement(arr, n);
// Display calculated result
System.out.println("\n Result : " + result);
}
public static void main(String[] args)
{
Subsequence task = new Subsequence();
// Define array of integer elements
int[] arr1 = {
8 , 4 , 7 , 5 , 1 , 3
};
int[] arr2 = {
9 , 10 , 3 , 4 , 8 , 7 , 10
};
int[] arr3 = {
7 , 6 , 5 , 1
};
// Test Case A
// [ 8, 4, 7, 5, 1, 3]
// length of Longest increasing subsequence 2
// (8,7), (4, 5), (1,3)
// 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 = 2
n = arr2.length;
task.longestSubsequences(arr2, n);
// Test Case C
// [ 7 , 6, 5]
// length of Longest increasing subsequence 1
// (7),(6),(5)
// Result = 4
n = arr3.length;
task.longestSubsequences(arr3, n);
}
}input
8 4 7 5 1 3
Result : 3
9 10 3 4 8 7 10
Result : 2
7 6 5 1
Result : 4// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Count the number 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];
}
}
// Calculates the all number of longest increasing subsequence
void longestSubsequences(int arr[], int n)
{
if (n <= 0)
{
return;
}
// Define two auxiliary array
int length[n];
int counter[n];
// Define some auxiliary variables
int i = 0;
int j = 0;
int result = 0;
int max = 0;
// Set the initial value in auxiliary array
for (i = 0; i < n; i++)
{
length[i] = 1;
counter[i] = 1;
}
// Execute loop through by size of arr
for (i = 0; i < n; i++)
{
// calculate increasing subsequence length and count their size
for (j = 0; j < i; j++)
{
if (arr[i] > arr[j])
{
if (length[j] + 1 > length[i])
{
counter[i] = counter[j];
length[i] = length[j] + 1;
}
else
{
if (length[j] + 1 == length[i])
{
counter[i] += counter[j];
}
}
}
}
}
// Count the length of longest subsequence
for (i = 0; i < n; i++)
{
if (max < length[i])
{
// When gets new largest subsequence
max = length[i];
}
}
// Count the number of longest increasing subsequence in max length
for (i = 0; i < n; i++)
{
if (length[i] == max)
{
// Add the repeated subsequence of max length
result += counter[i];
}
}
// Display given array
this->printElement(arr, n);
// Display calculated result
cout << "\n Result : " << result << endl;
}
};
int main()
{
Subsequence *task = new Subsequence();
// Define array of integer elements
int arr1[] = {
8 , 4 , 7 , 5 , 1 , 3
};
int arr2[] = {
9 , 10 , 3 , 4 , 8 , 7 , 10
};
int arr3[] = {
7 , 6 , 5 , 1
};
// Test Case A
// [ 8, 4, 7, 5, 1, 3]
// length of Longest increasing subsequence 2
// (8,7), (4, 5), (1,3)
// 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 = 2
n = sizeof(arr2) / sizeof(arr2[0]);
task->longestSubsequences(arr2, n);
// Test Case C
// [ 7 , 6, 5]
// length of Longest increasing subsequence 1
// (7),(6),(5)
// Result = 4
n = sizeof(arr3) / sizeof(arr3[0]);
task->longestSubsequences(arr3, n);
return 0;
}input
8 4 7 5 1 3
Result : 3
9 10 3 4 8 7 10
Result : 2
7 6 5 1
Result : 4// Include namespace system
using System;
/*
Csharp Program
Count the number 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]);
}
}
// Calculates the all number of longest increasing subsequence
public void longestSubsequences(int[] arr, int n)
{
if (n <= 0)
{
return;
}
// Define two auxiliary array
int[] length = new int[n];
int[] counter = new int[n];
// Define some auxiliary variables
int i = 0;
int j = 0;
int result = 0;
int max = 0;
// Set the initial value in auxiliary array
for (i = 0; i < n; i++)
{
length[i] = 1;
counter[i] = 1;
}
// Execute loop through by size of arr
for (i = 0; i < n; i++)
{
// calculate increasing subsequence length and count their size
for (j = 0; j < i; j++)
{
if (arr[i] > arr[j])
{
if (length[j] + 1 > length[i])
{
counter[i] = counter[j];
length[i] = length[j] + 1;
}
else
{
if (length[j] + 1 == length[i])
{
counter[i] += counter[j];
}
}
}
}
}
// Count the length of longest subsequence
for (i = 0; i < n; i++)
{
if (max < length[i])
{
// When gets new largest subsequence
max = length[i];
}
}
// Count the number of longest increasing subsequence in max length
for (i = 0; i < n; i++)
{
if (length[i] == max)
{
// Add the repeated subsequence of max length
result += counter[i];
}
}
// Display given array
this.printElement(arr, n);
// Display calculated result
Console.WriteLine("\n Result : " + result);
}
public static void Main(String[] args)
{
Subsequence task = new Subsequence();
// Define array of integer elements
int[] arr1 = {
8 , 4 , 7 , 5 , 1 , 3
};
int[] arr2 = {
9 , 10 , 3 , 4 , 8 , 7 , 10
};
int[] arr3 = {
7 , 6 , 5 , 1
};
// Test Case A
// [ 8, 4, 7, 5, 1, 3]
// length of Longest increasing subsequence 2
// (8,7), (4, 5), (1,3)
// 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 = 2
n = arr2.Length;
task.longestSubsequences(arr2, n);
// Test Case C
// [ 7 , 6, 5]
// length of Longest increasing subsequence 1
// (7),(6),(5)
// Result = 4
n = arr3.Length;
task.longestSubsequences(arr3, n);
}
}input
8 4 7 5 1 3
Result : 3
9 10 3 4 8 7 10
Result : 2
7 6 5 1
Result : 4<?php
/*
Php Program
Count the number 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]);
}
}
// Calculates the all number of longest increasing subsequence
public function longestSubsequences($arr, $n)
{
if ($n <= 0)
{
return;
}
// Define two auxiliary array
// Set the initial value in auxiliary array
$length = array_fill(0, $n, 1);
$counter = array_fill(0, $n, 1);
// Define some auxiliary variables
$i = 0;
$j = 0;
$result = 0;
$max = 0;
// Execute loop through by size of arr
for ($i = 0; $i < $n; $i++)
{
// calculate increasing subsequence length and count their size
for ($j = 0; $j < $i; $j++)
{
if ($arr[$i] > $arr[$j])
{
if ($length[$j] + 1 > $length[$i])
{
$counter[$i] = $counter[$j];
$length[$i] = $length[$j] + 1;
}
else
{
if ($length[$j] + 1 == $length[$i])
{
$counter[$i] += $counter[$j];
}
}
}
}
}
// Count the length of longest subsequence
for ($i = 0; $i < $n; $i++)
{
if ($max < $length[$i])
{
// When gets new largest subsequence
$max = $length[$i];
}
}
// Count the number of longest increasing subsequence in max length
for ($i = 0; $i < $n; $i++)
{
if ($length[$i] == $max)
{
// Add the repeated subsequence of max length
$result += $counter[$i];
}
}
// Display given array
$this->printElement($arr, $n);
// Display calculated result
echo("\n Result : ".$result.
"\n");
}
}
function main()
{
$task = new Subsequence();
// Define array of integer elements
$arr1 = array(8, 4, 7, 5, 1, 3);
$arr2 = array(9, 10, 3, 4, 8, 7, 10);
$arr3 = array(7, 6, 5, 1);
// Test Case A
// [ 8, 4, 7, 5, 1, 3]
// length of Longest increasing subsequence 2
// (8,7), (4, 5), (1,3)
// 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 = 2
$n = count($arr2);
$task->longestSubsequences($arr2, $n);
// Test Case C
// [ 7 , 6, 5]
// length of Longest increasing subsequence 1
// (7),(6),(5)
// Result = 4
$n = count($arr3);
$task->longestSubsequences($arr3, $n);
}
main();input
8 4 7 5 1 3
Result : 3
9 10 3 4 8 7 10
Result : 2
7 6 5 1
Result : 4/*
Node JS Program
Count the number 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]);
}
}
// Calculates the all number of longest increasing subsequence
longestSubsequences(arr, n)
{
if (n <= 0)
{
return;
}
// Define two auxiliary array
// Set the initial value in auxiliary array
var length = Array(n).fill(1);
var counter = Array(n).fill(1);
// Define some auxiliary variables
var i = 0;
var j = 0;
var result = 0;
var max = 0;
// Execute loop through by size of arr
for (i = 0; i < n; i++)
{
// calculate increasing subsequence length and count their size
for (j = 0; j < i; j++)
{
if (arr[i] > arr[j])
{
if (length[j] + 1 > length[i])
{
counter[i] = counter[j];
length[i] = length[j] + 1;
}
else
{
if (length[j] + 1 == length[i])
{
counter[i] += counter[j];
}
}
}
}
}
// Count the length of longest subsequence
for (i = 0; i < n; i++)
{
if (max < length[i])
{
// When gets new largest subsequence
max = length[i];
}
}
// Count the number of longest increasing subsequence in max length
for (i = 0; i < n; i++)
{
if (length[i] == max)
{
// Add the repeated subsequence of max length
result += counter[i];
}
}
// Display given array
this.printElement(arr, n);
// Display calculated result
console.log("\n Result : " + result);
}
}
function main()
{
var task = new Subsequence();
// Define array of integer elements
var arr1 = [8, 4, 7, 5, 1, 3];
var arr2 = [9, 10, 3, 4, 8, 7, 10];
var arr3 = [7, 6, 5, 1];
// Test Case A
// [ 8, 4, 7, 5, 1, 3]
// length of Longest increasing subsequence 2
// (8,7), (4, 5), (1,3)
// 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 = 2
n = arr2.length;
task.longestSubsequences(arr2, n);
// Test Case C
// [ 7 , 6, 5]
// length of Longest increasing subsequence 1
// (7),(6),(5)
// Result = 4
n = arr3.length;
task.longestSubsequences(arr3, n);
}
main();input
8 4 7 5 1 3
Result : 3
9 10 3 4 8 7 10
Result : 2
7 6 5 1
Result : 4# Python 3 Program
# Count the number 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
# Calculates the all number of longest increasing subsequence
def longestSubsequences(self, arr, n) :
if (n <= 0) :
return
length = [1] * (n)
counter = [1] * (n)
i = 0
j = 0
result = 0
max = 0
# Execute loop through by size of arr
i = 0
while (i < n) :
# calculate increasing subsequence length and count their size
j = 0
while (j < i) :
if (arr[i] > arr[j]) :
if (length[j] + 1 > length[i]) :
counter[i] = counter[j]
length[i] = length[j] + 1
else :
if (length[j] + 1 == length[i]) :
counter[i] += counter[j]
j += 1
i += 1
# Count the length of longest subsequence
i = 0
while (i < n) :
if (max < length[i]) :
# When gets new largest subsequence
max = length[i]
i += 1
# Count the number of longest increasing subsequence in max length
i = 0
while (i < n) :
if (length[i] == max) :
# Add the repeated subsequence of max length
result += counter[i]
i += 1
# Display given list
self.printElement(arr, n)
# Display calculated result
print("\n Result : ", result)
def main() :
task = Subsequence()
arr1 = [8, 4, 7, 5, 1, 3]
arr2 = [9, 10, 3, 4, 8, 7, 10]
arr3 = [7, 6, 5, 1]
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 = 2
n = len(arr2)
task.longestSubsequences(arr2, n)
# Test Case C
# [ 7 , 6, 5]
# length of Longest increasing subsequence 1
# (7),(6),(5)
# Result = 4
n = len(arr3)
task.longestSubsequences(arr3, n)
if __name__ == "__main__": main()input
8 4 7 5 1 3
Result : 3
9 10 3 4 8 7 10
Result : 2
7 6 5 1
Result : 4# Ruby Program
# Count the number 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
# Calculates the all number of longest increasing subsequence
def longestSubsequences(arr, n)
if (n <= 0)
return
end
# Define two auxiliary array
# Set the initial value in auxiliary array
length = Array.new(n) {1}
counter = Array.new(n) {1}
# Define some auxiliary variables
i = 0
j = 0
result = 0
max = 0
# Execute loop through by size of arr
i = 0
while (i < n)
# calculate increasing subsequence length and count their size
j = 0
while (j < i)
if (arr[i] > arr[j])
if (length[j] + 1 > length[i])
counter[i] = counter[j]
length[i] = length[j] + 1
else
if (length[j] + 1 == length[i])
counter[i] += counter[j]
end
end
end
j += 1
end
i += 1
end
# Count the length of longest subsequence
i = 0
while (i < n)
if (max < length[i])
# When gets new largest subsequence
max = length[i]
end
i += 1
end
# Count the number of longest increasing subsequence in max length
i = 0
while (i < n)
if (length[i] == max)
# Add the repeated subsequence of max length
result += counter[i]
end
i += 1
end
# Display given array
self.printElement(arr, n)
# Display calculated result
print("\n Result : ", result, "\n")
end
end
def main()
task = Subsequence.new()
# Define array of integer elements
arr1 = [8, 4, 7, 5, 1, 3]
arr2 = [9, 10, 3, 4, 8, 7, 10]
arr3 = [7, 6, 5, 1]
# Test Case A
# [ 8, 4, 7, 5, 1, 3]
# length of Longest increasing subsequence 2
# (8,7), (4, 5), (1,3)
# 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 = 2
n = arr2.length
task.longestSubsequences(arr2, n)
# Test Case C
# [ 7 , 6, 5]
# length of Longest increasing subsequence 1
# (7),(6),(5)
# Result = 4
n = arr3.length
task.longestSubsequences(arr3, n)
end
main()input
8 4 7 5 1 3
Result : 3
9 10 3 4 8 7 10
Result : 2
7 6 5 1
Result : 4
/*
Scala Program
Count the number 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;
}
}
// Calculates the all number of longest increasing subsequence
def longestSubsequences(arr: Array[Int], n: Int): Unit = {
if (n <= 0)
{
return;
}
// Define two auxiliary array
// Set the initial value in auxiliary array
var length: Array[Int] = Array.fill[Int](n)(1);
var counter: Array[Int] = Array.fill[Int](n)(1);
// Define some auxiliary variables
var i: Int = 0;
var j: Int = 0;
var result: Int = 0;
var max: Int = 0;
// Execute loop through by size of arr
i = 0;
while (i < n)
{
// calculate increasing subsequence length and count their size
j = 0;
while (j < i)
{
if (arr(i) > arr(j))
{
if (length(j) + 1 > length(i))
{
counter(i) = counter(j);
length(i) = length(j) + 1;
}
else
{
if (length(j) + 1 == length(i))
{
counter(i) += counter(j);
}
}
}
j += 1;
}
i += 1;
}
// Count the length of longest subsequence
i = 0;
while (i < n)
{
if (max < length(i))
{
// When gets new largest subsequence
max = length(i);
}
i += 1;
}
// Count the number of longest increasing subsequence in max length
i = 0;
while (i < n)
{
if (length(i) == max)
{
// Add the repeated subsequence of max length
result += counter(i);
}
i += 1;
}
// Display given array
printElement(arr, n);
// Display calculated result
println("\n Result : " + 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, 3);
var arr2: Array[Int] = Array(9, 10, 3, 4, 8, 7, 10);
var arr3: Array[Int] = Array(7, 6, 5, 1);
// Test Case A
// [ 8, 4, 7, 5, 1, 3]
// length of Longest increasing subsequence 2
// (8,7), (4, 5), (1,3)
// 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 = 2
n = arr2.length;
task.longestSubsequences(arr2, n);
// Test Case C
// [ 7 , 6, 5]
// length of Longest increasing subsequence 1
// (7),(6),(5)
// Result = 4
n = arr3.length;
task.longestSubsequences(arr3, n);
}
}input
8 4 7 5 1 3
Result : 3
9 10 3 4 8 7 10
Result : 2
7 6 5 1
Result : 4/*
Swift 4 Program
Count the number 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;
}
}
// Calculates the all number of longest increasing subsequence
func longestSubsequences(_ arr: [Int], _ n: Int)
{
if (n <= 0)
{
return;
}
// Define two auxiliary array
// Set the initial value in auxiliary array
var length: [Int] = Array(repeating: 1, count: n);
var counter: [Int] = Array(repeating: 1, count: n);
// Define some auxiliary variables
var i: Int = 0;
var j: Int = 0;
var result: Int = 0;
var max: Int = 0;
// Execute loop through by size of arr
i = 0;
while (i < n)
{
// calculate increasing subsequence length and count their size
j = 0;
while (j < i)
{
if (arr[i] > arr[j])
{
if (length[j] + 1 > length[i])
{
counter[i] = counter[j];
length[i] = length[j] + 1;
}
else
{
if (length[j] + 1 == length[i])
{
counter[i] += counter[j];
}
}
}
j += 1;
}
i += 1;
}
// Count the length of longest subsequence
i = 0;
while (i < n)
{
if (max < length[i])
{
// When gets new largest subsequence
max = length[i];
}
i += 1;
}
// Count the number of longest increasing subsequence in max length
i = 0;
while (i < n)
{
if (length[i] == max)
{
// Add the repeated subsequence of max length
result += counter[i];
}
i += 1;
}
// Display given array
self.printElement(arr, n);
// Display calculated result
print("\n Result : ", result);
}
}
func main()
{
let task: Subsequence = Subsequence();
// Define array of integer elements
let arr1: [Int] = [8, 4, 7, 5, 1, 3];
let arr2: [Int] = [9, 10, 3, 4, 8, 7, 10];
let arr3: [Int] = [7, 6, 5, 1];
// Test Case A
// [ 8, 4, 7, 5, 1, 3]
// length of Longest increasing subsequence 2
// (8,7), (4, 5), (1,3)
// 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 = 2
n = arr2.count;
task.longestSubsequences(arr2, n);
// Test Case C
// [ 7 , 6, 5]
// length of Longest increasing subsequence 1
// (7),(6),(5)
// Result = 4
n = arr3.count;
task.longestSubsequences(arr3, n);
}
main();input
8 4 7 5 1 3
Result : 3
9 10 3 4 8 7 10
Result : 2
7 6 5 1
Result : 4/*
Kotlin Program
Count the number 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;
}
}
// Calculates the all number of longest increasing subsequence
fun longestSubsequences(arr: Array < Int > , n: Int): Unit
{
if (n <= 0)
{
return;
}
// Define two auxiliary array
// Set the initial value in auxiliary array
val length: Array < Int > = Array(n)
{
1
};
val counter: Array < Int > = Array(n)
{
1
};
// Define some auxiliary variables
var i: Int = 0;
var j: Int = 0;
var result: Int = 0;
var max: Int = 0;
while (i < n)
{
while (j < i)
{
if (arr[i] > arr[j])
{
if (length[j] + 1 > length[i])
{
counter[i] = counter[j];
length[i] = length[j] + 1;
}
else
{
if (length[j] + 1 == length[i])
{
counter[i] += counter[j];
}
}
}
j += 1;
}
i += 1;
j = 0;
}
i = 0;
while (i < n)
{
if (max < length[i])
{
// When gets new largest subsequence
max = length[i];
}
i += 1;
}
i = 0;
while (i < n)
{
if (length[i] == max)
{
// Add the repeated subsequence of max length
result += counter[i];
}
i += 1;
}
// Display given array
this.printElement(arr, n);
// Display calculated result
println("\n Result : " + 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, 3);
val arr2: Array < Int > = arrayOf(9, 10, 3, 4, 8, 7, 10);
val arr3: Array < Int > = arrayOf(7, 6, 5, 1);
// Test Case A
// [ 8, 4, 7, 5, 1, 3]
// length of Longest increasing subsequence 2
// (8,7), (4, 5), (1,3)
// 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 = 2
n = arr2.count();
task.longestSubsequences(arr2, n);
// Test Case C
// [ 7 , 6, 5]
// length of Longest increasing subsequence 1
// (7),(6),(5)
// Result = 4
n = arr3.count();
task.longestSubsequences(arr3, n);
}input
8 4 7 5 1 3
Result : 3
9 10 3 4 8 7 10
Result : 2
7 6 5 1
Result : 4Explanation
The given code solves the problem by using two auxiliary arrays: length[] and counter[]. The length[] array stores the length of the longest increasing subsequence ending at each position in the array, and the counter[] array stores the count of subsequences with the same length as the longest subsequence ending at each position.
The algorithm iterates through the array and for each element, it checks all the previous elements to find the longest increasing subsequence ending at that position. It updates the length[] and counter[] arrays accordingly. Finally, it finds the maximum length of the longest subsequence and counts the number of subsequences with that length.
Resultant Output Explanation
The given code includes three test cases to demonstrate its functionality:
Test Case A:
Array: [8, 4, 7, 5, 1, 3]
Length of the longest increasing subsequence: 2
Longest increasing subsequences: (8, 7), (4, 5), (1, 3)
Result: 3
Test Case B:
Array: [9, 10, 3, 4, 8, 7, 10]
Length of the longest increasing subsequence: 4
Longest increasing subsequences: (3, 4, 8, 10), (3, 4, 7, 10)
Result: 2
Test Case C:
Array: [7, 6, 5, 1]
Length of the longest increasing subsequence: 1
Longest increasing subsequences: (7), (6), (5)
Result: 4
Time Complexity
The time complexity of this algorithm is O(n^2), where n is the size of the input array. This is because the algorithm uses nested loops to compare each element with the previous elements, resulting in a quadratic time complexity.
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