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)
	{
		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 : 4


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







© 2021, kalkicode.com, All rights reserved