# Count the number of longest increasing subsequence

Here given code implementation process.

``````// 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)
{
// 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;
// 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;
// Test Case C
// [ 7 , 6, 5]
// length of Longest increasing subsequence 1
// (7),(6),(5)
//  Result = 4
n = arr3.length;
}
}``````

#### 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()
{
// 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]);
// 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]);
// Test Case C
// [ 7 , 6, 5]
// length of Longest increasing subsequence 1
// (7),(6),(5)
//  Result = 4
n = sizeof(arr3) / sizeof(arr3[0]);
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)
{
// 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;
// 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;
// Test Case C
// [ 7 , 6, 5]
// length of Longest increasing subsequence 1
// (7),(6),(5)
//  Result = 4
n = arr3.Length;
}
}``````

#### 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()
{
// 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);
// 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);
// Test Case C
// [ 7 , 6, 5]
// length of Longest increasing subsequence 1
// (7),(6),(5)
//  Result = 4
\$n = count(\$arr3);
}
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()
{
// 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;
// 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;
// Test Case C
// [ 7 , 6, 5]
// length of Longest increasing subsequence 1
// (7),(6),(5)
//  Result = 4
n = arr3.length;
}
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() :
arr1 = [8, 4, 7, 5, 1, 3]
arr2 = [9, 10, 3, 4, 8, 7, 10]
arr3 = [7, 6, 5, 1]
n = len(arr1)
#  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)
#  Test Case C
#  [ 7 , 6, 5]
#  length of Longest increasing subsequence 1
#  (7),(6),(5)
#   Result = 4
n = len(arr3)

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()
#  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
#  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
#  Test Case C
#  [ 7 , 6, 5]
#  length of Longest increasing subsequence 1
#  (7),(6),(5)
#   Result = 4
n = arr3.length
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;
// 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;
// Test Case C
// [ 7 , 6, 5]
// length of Longest increasing subsequence 1
// (7),(6),(5)
//  Result = 4
n = arr3.length;
}
}``````

#### 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()
{
// 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;
// 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;
// Test Case C
// [ 7 , 6, 5]
// length of Longest increasing subsequence 1
// (7),(6),(5)
//  Result = 4
n = arr3.count;
}
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
{
// 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();
// 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();
// Test Case C
// [ 7 , 6, 5]
// length of Longest increasing subsequence 1
// (7),(6),(5)
//  Result = 4
n = arr3.count();
}``````

#### input

``````  8  4  7  5  1  3
Result : 3
9  10  3  4  8  7  10
Result : 2
7  6  5  1
Result : 4``````

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.