Find circular longest increasing subsequence
Here given code implementation process.
// C Program
// Find circular 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]);
}
}
int longestIncSubsequences(int arr[], int s, int e)
{
// Define auxiliary array
int length[e];
// Define some auxiliary variables
int i = 0;
int j = 0;
int ans = 1;
// Set the initial value in auxiliary array
for (i = 0; i < e; i++)
{
length[i] = 1;
}
// Execute loop through by size of array
for (i = s + 1; i < e; i++)
{
// calculate increasing subsequence length
for (j = s; j < i; j++)
{
if (arr[i] > arr[j])
{
if (length[j] + 1 > length[i])
{
length[i] = length[j] + 1;
if (length[i] > ans)
{
ans = length[i];
}
}
}
}
}
return ans;
}
int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
void longestSubsequences(int arr[], int n)
{
if (n <= 0)
{
return;
}
int result = 0;
int auxiliary[n *2];
for (int i = 0; i < n; ++i)
{
auxiliary[i] = arr[i];
auxiliary[i + n] = arr[i];
}
for (int i = 0; i < n; ++i)
{
result = maxValue(result,
longestIncSubsequences(auxiliary, i, i + n));
}
// 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[] = {
7 , 8 , 6 , 9 , 4 , 5 , 6
};
int arr2[] = {
7 , 9 , 3 , 4 , 8 , 7 , 2
};
int arr3[] = {
12 , 11 , 10 , 7 , 8 , 1 , 2 , 9 , 3
};
// Test A
// [ 7, 8, 6, 9, 4 , 5, 6]
// length of Longest increasing subsequence 6
// (4 , 5, 6, 7, 8, 9)
// Result = 6
int n = sizeof(arr1) / sizeof(arr1[0]);
longestSubsequences(arr1, n);
// Test B
// arr = [ 7 , 9 , 3 , 4 , 8 , 7 , 2]
// length of Longest increasing subsequence 4
// (3, 4, 7 , 9), (3 , 4 , 8, 9) etc
// Result = 4
n = sizeof(arr2) / sizeof(arr2[0]);
longestSubsequences(arr2, n);
// Test C
// arr = [ 12 11 10 7 8 1 2 9 3]
// [1, 2, 3, 7, 8]
// Result : 5
n = sizeof(arr3) / sizeof(arr3[0]);
longestSubsequences(arr3, n);
return 0;
}
Output
7 8 6 9 4 5 6
Length of Longest increasing subsequence is : 6
7 9 3 4 8 7 2
Length of Longest increasing subsequence is : 4
12 11 10 7 8 1 2 9 3
Length of Longest increasing subsequence is : 5
// Java program for
// Find circular 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 int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
public int longestIncSubsequences(int[] arr, int s, int e)
{
// Define auxiliary array
int[] length = new int[e];
// Define some auxiliary variables
int i = 0;
int j = 0;
int ans = 1;
// Set the initial value in auxiliary array
for (i = 0; i < e; i++)
{
length[i] = 1;
}
// Execute loop through by size of array
for (i = s + 1; i < e; i++)
{
// calculate increasing subsequence length
for (j = s; j < i; j++)
{
if (arr[i] > arr[j])
{
if (length[j] + 1 > length[i])
{
length[i] = length[j] + 1;
if (length[i] > ans)
{
ans = length[i];
}
}
}
}
}
return ans;
}
// Handles the request to finding circular increasing subsequence
public void findCireculLISS(int[] arr, int n)
{
if (n <= 0)
{
return;
}
int result = 0;
// Auxiliary array which contains the double copy of original array
int[] auxiliary = new int[n * 2];
for (int i = 0; i < n; ++i)
{
auxiliary[i] = arr[i];
// Append similar element at the end
auxiliary[i + n] = arr[i];
}
for (int i = 0; i < n; ++i)
{
result = maxValue(result,
longestIncSubsequences(auxiliary, i, i + n));
}
// Display given array
printElement(arr, n);
// Display calculated result
System.out.println("\n Length of CLIS is : " + result);
}
public static void main(String[] args)
{
Subsequence task = new Subsequence();
// Define array of integer elements
int[] arr1 = {
7 , 8 , 6 , 9 , 4 , 5 , 6
};
int[] arr2 = {
7 , 9 , 3 , 4 , 8 , 7 , 2
};
int[] arr3 = {
12 , 11 , 10 , 7 , 8 , 1 , 2 , 9 , 3
};
// Test A
// [ 7, 8, 6, 9, 4 , 5, 6]
// length of Longest circular increasing subsequence 6
// (4 , 5, 6, 7, 8, 9)
// Result = 6
int n = arr1.length;
task.findCireculLISS(arr1, n);
// Test B
// arr = [ 7 , 9 , 3 , 4 , 8 , 7 , 2]
// length of Longest circular increasing subsequence 4
// (3, 4, 7 , 9), (3 , 4 , 8, 9) etc
// Result = 4
n = arr2.length;
task.findCireculLISS(arr2, n);
// Test C
// arr = [ 12 11 10 7 8 1 2 9 3]
// [1, 2, 3, 7, 8]
// Result : 5
n = arr3.length;
task.findCireculLISS(arr3, n);
}
}
Output
7 8 6 9 4 5 6
Length of CLIS is : 6
7 9 3 4 8 7 2
Length of CLIS is : 4
12 11 10 7 8 1 2 9 3
Length of CLIS is : 5
// Include header file
#include <iostream>
using namespace std;
// C++ program for
// Find circular 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];
}
}
int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
int longestIncSubsequences(int arr[], int s, int e)
{
// Define auxiliary array
int length[e];
// Define some auxiliary variables
int i = 0;
int j = 0;
int ans = 1;
// Set the initial value in auxiliary array
for (i = 0; i < e; i++)
{
length[i] = 1;
}
// Execute loop through by size of array
for (i = s + 1; i < e; i++)
{
// calculate increasing subsequence length
for (j = s; j < i; j++)
{
if (arr[i] > arr[j])
{
if (length[j] + 1 > length[i])
{
length[i] = length[j] + 1;
if (length[i] > ans)
{
ans = length[i];
}
}
}
}
}
return ans;
}
// Handles the request to finding circular increasing subsequence
void findCireculLISS(int arr[], int n)
{
if (n <= 0)
{
return;
}
int result = 0;
// Auxiliary array which contains the double copy of original array
int auxiliary[n *2];
for (int i = 0; i < n; ++i)
{
auxiliary[i] = arr[i];
// Append similar element at the end
auxiliary[i + n] = arr[i];
}
for (int i = 0; i < n; ++i)
{
result = this->maxValue(result,
this->longestIncSubsequences(
auxiliary, i, i + n));
}
// Display given array
this->printElement(arr, n);
// Display calculated result
cout << "\n Length of CLIS is : " << result << endl;
}
};
int main()
{
Subsequence *task = new Subsequence();
// Define array of integer elements
int arr1[] = {
7 , 8 , 6 , 9 , 4 , 5 , 6
};
int arr2[] = {
7 , 9 , 3 , 4 , 8 , 7 , 2
};
int arr3[] = {
12 , 11 , 10 , 7 , 8 , 1 , 2 , 9 , 3
};
// Test A
// [ 7, 8, 6, 9, 4 , 5, 6]
// length of Longest circular increasing subsequence 6
// (4 , 5, 6, 7, 8, 9)
// Result = 6
int n = sizeof(arr1) / sizeof(arr1[0]);
task->findCireculLISS(arr1, n);
// Test B
// arr = [ 7 , 9 , 3 , 4 , 8 , 7 , 2]
// length of Longest circular increasing subsequence 4
// (3, 4, 7 , 9), (3 , 4 , 8, 9) etc
// Result = 4
n = sizeof(arr2) / sizeof(arr2[0]);
task->findCireculLISS(arr2, n);
// Test C
// arr = [ 12 11 10 7 8 1 2 9 3]
// [1, 2, 3, 7, 8]
// Result : 5
n = sizeof(arr3) / sizeof(arr3[0]);
task->findCireculLISS(arr3, n);
return 0;
}
Output
7 8 6 9 4 5 6
Length of CLIS is : 6
7 9 3 4 8 7 2
Length of CLIS is : 4
12 11 10 7 8 1 2 9 3
Length of CLIS is : 5
// Include namespace system
using System;
// Csharp program for
// Find circular 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 int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
public int longestIncSubsequences(int[] arr, int s, int e)
{
// Define auxiliary array
int[] length = new int[e];
// Define some auxiliary variables
int i = 0;
int j = 0;
int ans = 1;
// Set the initial value in auxiliary array
for (i = 0; i < e; i++)
{
length[i] = 1;
}
// Execute loop through by size of array
for (i = s + 1; i < e; i++)
{
// calculate increasing subsequence length
for (j = s; j < i; j++)
{
if (arr[i] > arr[j])
{
if (length[j] + 1 > length[i])
{
length[i] = length[j] + 1;
if (length[i] > ans)
{
ans = length[i];
}
}
}
}
}
return ans;
}
// Handles the request to finding circular increasing subsequence
public void findCireculLISS(int[] arr, int n)
{
if (n <= 0)
{
return;
}
int result = 0;
// Auxiliary array which contains the double copy of original array
int[] auxiliary = new int[n * 2];
for (int i = 0; i < n; ++i)
{
auxiliary[i] = arr[i];
// Append similar element at the end
auxiliary[i + n] = arr[i];
}
for (int i = 0; i < n; ++i)
{
result = this.maxValue(result,
this.longestIncSubsequences(
auxiliary, i, i + n));
}
// Display given array
this.printElement(arr, n);
// Display calculated result
Console.WriteLine("\n Length of CLIS is : " + result);
}
public static void Main(String[] args)
{
Subsequence task = new Subsequence();
// Define array of integer elements
int[] arr1 = {
7 , 8 , 6 , 9 , 4 , 5 , 6
};
int[] arr2 = {
7 , 9 , 3 , 4 , 8 , 7 , 2
};
int[] arr3 = {
12 , 11 , 10 , 7 , 8 , 1 , 2 , 9 , 3
};
// Test A
// [ 7, 8, 6, 9, 4 , 5, 6]
// length of Longest circular increasing subsequence 6
// (4 , 5, 6, 7, 8, 9)
// Result = 6
int n = arr1.Length;
task.findCireculLISS(arr1, n);
// Test B
// arr = [ 7 , 9 , 3 , 4 , 8 , 7 , 2]
// length of Longest circular increasing subsequence 4
// (3, 4, 7 , 9), (3 , 4 , 8, 9) etc
// Result = 4
n = arr2.Length;
task.findCireculLISS(arr2, n);
// Test C
// arr = [ 12 11 10 7 8 1 2 9 3]
// [1, 2, 3, 7, 8]
// Result : 5
n = arr3.Length;
task.findCireculLISS(arr3, n);
}
}
Output
7 8 6 9 4 5 6
Length of CLIS is : 6
7 9 3 4 8 7 2
Length of CLIS is : 4
12 11 10 7 8 1 2 9 3
Length of CLIS is : 5
package main
import "fmt"
// Go program for
// Find circular 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) maxValue(a, b int) int {
if a > b {
return a
}
return b
}
func(this Subsequence) longestIncSubsequences(arr[] int,
s int, e int) int {
// Define auxiliary array
var length = make([] int, e)
// Define some auxiliary variables
var i int = 0
var j int = 0
var ans int = 1
// Set the initial value in auxiliary array
for i = 0 ; i < e ; i++ {
length[i] = 1
}
// Execute loop through by size of array
for i = s + 1 ; i < e ; i++ {
// calculate increasing subsequence length
for j = s ; j < i ; j++ {
if arr[i] > arr[j] {
if length[j] + 1 > length[i] {
length[i] = length[j] + 1
if length[i] > ans {
ans = length[i]
}
}
}
}
}
return ans
}
// Handles the request to finding circular increasing subsequence
func(this Subsequence) findCireculLISS(arr[] int, n int) {
if n <= 0 {
return
}
var result int = 0
// Auxiliary array which contains the double copy of original array
var auxiliary = make([] int, n * 2)
for i := 0 ; i < n ; i++ {
auxiliary[i] = arr[i]
// Append similar element at the end
auxiliary[i + n] = arr[i]
}
for i := 0 ; i < n ; i++ {
result = this.maxValue(result,
this.longestIncSubsequences(auxiliary, i, i + n))
}
// Display given array
this.printElement(arr, n)
// Display calculated result
fmt.Println("\n Length of CLIS is : ", result)
}
func main() {
var task * Subsequence = getSubsequence()
// Define array of integer elements
var arr1 = [] int {
7,
8,
6,
9,
4,
5,
6,
}
var arr2 = [] int {
7,
9,
3,
4,
8,
7,
2,
}
var arr3 = [] int {
12,
11,
10,
7,
8,
1,
2,
9,
3,
}
// Test A
// [ 7, 8, 6, 9, 4 , 5, 6]
// length of Longest circular increasing subsequence 6
// (4 , 5, 6, 7, 8, 9)
// Result = 6
var n int = len(arr1)
task.findCireculLISS(arr1, n)
// Test B
// arr = [ 7 , 9 , 3 , 4 , 8 , 7 , 2]
// length of Longest circular increasing subsequence 4
// (3, 4, 7 , 9), (3 , 4 , 8, 9) etc
// Result = 4
n = len(arr2)
task.findCireculLISS(arr2, n)
// Test C
// arr = [ 12 11 10 7 8 1 2 9 3]
// [1, 2, 3, 7, 8]
// Result : 5
n = len(arr3)
task.findCireculLISS(arr3, n)
}
Output
7 8 6 9 4 5 6
Length of CLIS is : 6
7 9 3 4 8 7 2
Length of CLIS is : 4
12 11 10 7 8 1 2 9 3
Length of CLIS is : 5
<?php
// Php program for
// Find circular 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 maxValue($a, $b)
{
if ($a > $b)
{
return $a;
}
return $b;
}
public function longestIncSubsequences($arr, $s, $e)
{
// Define auxiliary list
// Set initial 1 length of each element
$length = array_fill(0, $e, 1);
// Define some auxiliary variables
$i = 0;
$j = 0;
$ans = 1;
// Execute loop through by size of array
for ($i = $s + 1; $i < $e; $i++)
{
// calculate increasing subsequence length
for ($j = $s; $j < $i; $j++)
{
if ($arr[$i] > $arr[$j])
{
if ($length[$j] + 1 > $length[$i])
{
$length[$i] = $length[$j] + 1;
if ($length[$i] > $ans)
{
$ans = $length[$i];
}
}
}
}
}
return $ans;
}
// Handles the request to finding circular increasing subsequence
public function findCireculLISS($arr, $n)
{
if ($n <= 0)
{
return;
}
$result = 0;
// Auxiliary array which contains the double copy of original array
$auxiliary = array_fill(0, $n * 2, 0);
for ($i = 0; $i < $n; ++$i)
{
$auxiliary[$i] = $arr[$i];
// Append similar element at the end
$auxiliary[$i + $n] = $arr[$i];
}
for ($i = 0; $i < $n; ++$i)
{
$result = $this->maxValue($result,
$this->longestIncSubsequences($auxiliary,
$i, $i + $n));
}
// Display given array
$this->printElement($arr, $n);
// Display calculated result
echo("\n Length of CLIS is : ".$result.
"\n");
}
}
function main()
{
$task = new Subsequence();
// Define array of integer elements
$arr1 = array(7, 8, 6, 9, 4, 5, 6);
$arr2 = array(7, 9, 3, 4, 8, 7, 2);
$arr3 = array(12, 11, 10, 7, 8, 1, 2, 9, 3);
// Test A
// [ 7, 8, 6, 9, 4 , 5, 6]
// length of Longest circular increasing subsequence 6
// (4 , 5, 6, 7, 8, 9)
// Result = 6
$n = count($arr1);
$task->findCireculLISS($arr1, $n);
// Test B
// arr = [ 7 , 9 , 3 , 4 , 8 , 7 , 2]
// length of Longest circular increasing subsequence 4
// (3, 4, 7 , 9), (3 , 4 , 8, 9) etc
// Result = 4
$n = count($arr2);
$task->findCireculLISS($arr2, $n);
// Test C
// arr = [ 12 11 10 7 8 1 2 9 3]
// [1, 2, 3, 7, 8]
// Result : 5
$n = count($arr3);
$task->findCireculLISS($arr3, $n);
}
main();
Output
7 8 6 9 4 5 6
Length of CLIS is : 6
7 9 3 4 8 7 2
Length of CLIS is : 4
12 11 10 7 8 1 2 9 3
Length of CLIS is : 5
// Node JS program for
// Find circular 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]);
}
}
maxValue(a, b)
{
if (a > b)
{
return a;
}
return b;
}
longestIncSubsequences(arr, s, e)
{
// Define auxiliary list
// Set initial 1 length of each element
var length = Array(e).fill(1);
// Define some auxiliary variables
var i = 0;
var j = 0;
var ans = 1;
// Execute loop through by size of array
for (i = s + 1; i < e; i++)
{
// calculate increasing subsequence length
for (j = s; j < i; j++)
{
if (arr[i] > arr[j])
{
if (length[j] + 1 > length[i])
{
length[i] = length[j] + 1;
if (length[i] > ans)
{
ans = length[i];
}
}
}
}
}
return ans;
}
// Handles the request to finding circular increasing subsequence
findCireculLISS(arr, n)
{
if (n <= 0)
{
return;
}
var result = 0;
// Auxiliary array which contains the double copy of original array
var auxiliary = Array(n * 2).fill(0);
for (var i = 0; i < n; ++i)
{
auxiliary[i] = arr[i];
// Append similar element at the end
auxiliary[i + n] = arr[i];
}
for (var i = 0; i < n; ++i)
{
result = this.maxValue(result, this.longestIncSubsequences(auxiliary, i, i + n));
}
// Display given array
this.printElement(arr, n);
// Display calculated result
console.log("\n Length of CLIS is : " + result);
}
}
function main()
{
var task = new Subsequence();
// Define array of integer elements
var arr1 = [7, 8, 6, 9, 4, 5, 6];
var arr2 = [7, 9, 3, 4, 8, 7, 2];
var arr3 = [12, 11, 10, 7, 8, 1, 2, 9, 3];
// Test A
// [ 7, 8, 6, 9, 4 , 5, 6]
// length of Longest circular increasing subsequence 6
// (4 , 5, 6, 7, 8, 9)
// Result = 6
var n = arr1.length;
task.findCireculLISS(arr1, n);
// Test B
// arr = [ 7 , 9 , 3 , 4 , 8 , 7 , 2]
// length of Longest circular increasing subsequence 4
// (3, 4, 7 , 9), (3 , 4 , 8, 9) etc
// Result = 4
n = arr2.length;
task.findCireculLISS(arr2, n);
// Test C
// arr = [ 12 11 10 7 8 1 2 9 3]
// [1, 2, 3, 7, 8]
// Result : 5
n = arr3.length;
task.findCireculLISS(arr3, n);
}
main();
Output
7 8 6 9 4 5 6
Length of CLIS is : 6
7 9 3 4 8 7 2
Length of CLIS is : 4
12 11 10 7 8 1 2 9 3
Length of CLIS is : 5
# Python 3 program for
# Find circular 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 maxValue(self, a, b) :
if (a > b) :
return a
return b
def longestIncSubsequences(self, arr, s, e) :
# Define auxiliary list
# Set initial 1 length of each element
length = [1] * (e)
# Define some auxiliary variables
i = 0
j = 0
ans = 1
i = s + 1
# Execute loop through by size of list
while (i < e) :
j = s
# 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] > ans) :
ans = length[i]
j += 1
i += 1
return ans
# Handles the request to finding circular increasing subsequence
def findCireculLISS(self, arr, n) :
if (n <= 0) :
return
result = 0
# Auxiliary list which contains the double copy of original list
auxiliary = [0] * (n * 2)
i = 0
while (i < n) :
auxiliary[i] = arr[i]
# Append similar element at the end
auxiliary[i + n] = arr[i]
i += 1
i = 0
while (i < n) :
result = self.maxValue(result, self.longestIncSubsequences(auxiliary, i, i + n))
i += 1
# Display given list
self.printElement(arr, n)
# Display calculated result
print("\n Length of CLIS is : ", result)
def main() :
task = Subsequence()
# Define list of integer elements
arr1 = [7, 8, 6, 9, 4, 5, 6]
arr2 = [7, 9, 3, 4, 8, 7, 2]
arr3 = [12, 11, 10, 7, 8, 1, 2, 9, 3]
# Test A
# [ 7, 8, 6, 9, 4 , 5, 6]
# length of Longest circular increasing subsequence 6
# (4 , 5, 6, 7, 8, 9)
# Result = 6
n = len(arr1)
task.findCireculLISS(arr1, n)
# Test B
# arr = [ 7 , 9 , 3 , 4 , 8 , 7 , 2]
# length of Longest circular increasing subsequence 4
# (3, 4, 7 , 9), (3 , 4 , 8, 9) etc
# Result = 4
n = len(arr2)
task.findCireculLISS(arr2, n)
# Test C
# arr = [ 12 11 10 7 8 1 2 9 3]
# [1, 2, 3, 7, 8]
# Result : 5
n = len(arr3)
task.findCireculLISS(arr3, n)
if __name__ == "__main__": main()
Output
7 8 6 9 4 5 6
Length of CLIS is : 6
7 9 3 4 8 7 2
Length of CLIS is : 4
12 11 10 7 8 1 2 9 3
Length of CLIS is : 5
# Ruby program for
# Find circular 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 maxValue(a, b)
if (a > b)
return a
end
return b
end
def longestIncSubsequences(arr, s, e)
# Define auxiliary list
# Set initial 1 length of each element
length = Array.new(e) {1}
# Define some auxiliary variables
i = 0
j = 0
ans = 1
i = s + 1
# Execute loop through by size of array
while (i < e)
j = s
# 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] > ans)
ans = length[i]
end
end
end
j += 1
end
i += 1
end
return ans
end
# Handles the request to finding circular increasing subsequence
def findCireculLISS(arr, n)
if (n <= 0)
return
end
result = 0
# Auxiliary array which contains the double copy of original array
auxiliary = Array.new(n * 2) {0}
i = 0
while (i < n)
auxiliary[i] = arr[i]
# Append similar element at the end
auxiliary[i + n] = arr[i]
i += 1
end
i = 0
while (i < n)
result = self.maxValue(result,
self.longestIncSubsequences(auxiliary, i, i + n))
i += 1
end
# Display given array
self.printElement(arr, n)
# Display calculated result
print("\n Length of CLIS is : ", result, "\n")
end
end
def main()
task = Subsequence.new()
# Define array of integer elements
arr1 = [7, 8, 6, 9, 4, 5, 6]
arr2 = [7, 9, 3, 4, 8, 7, 2]
arr3 = [12, 11, 10, 7, 8, 1, 2, 9, 3]
# Test A
# [ 7, 8, 6, 9, 4 , 5, 6]
# length of Longest circular increasing subsequence 6
# (4 , 5, 6, 7, 8, 9)
# Result = 6
n = arr1.length
task.findCireculLISS(arr1, n)
# Test B
# arr = [ 7 , 9 , 3 , 4 , 8 , 7 , 2]
# length of Longest circular increasing subsequence 4
# (3, 4, 7 , 9), (3 , 4 , 8, 9) etc
# Result = 4
n = arr2.length
task.findCireculLISS(arr2, n)
# Test C
# arr = [ 12 11 10 7 8 1 2 9 3]
# [1, 2, 3, 7, 8]
# Result : 5
n = arr3.length
task.findCireculLISS(arr3, n)
end
main()
Output
7 8 6 9 4 5 6
Length of CLIS is : 6
7 9 3 4 8 7 2
Length of CLIS is : 4
12 11 10 7 8 1 2 9 3
Length of CLIS is : 5
// Scala program for
// Find circular 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 maxValue(a: Int, b: Int): Int = {
if (a > b)
{
return a;
}
return b;
}
def longestIncSubsequences(arr: Array[Int], s: Int, e: Int): Int = {
// Define auxiliary list
// Set initial 1 length of each element
var length: Array[Int] = Array.fill[Int](e)(1);
// Define some auxiliary variables
var i: Int = s + 1;
var j: Int = 0;
var ans: Int = 1;
// Execute loop through by size of array
while (i < e)
{
j = s;
// 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) > ans)
{
ans = length(i);
}
}
}
j += 1;
}
i += 1;
}
return ans;
}
// Handles the request to finding circular increasing subsequence
def findCireculLISS(arr: Array[Int], n: Int): Unit = {
if (n <= 0)
{
return;
}
var result: Int = 0;
// Auxiliary array which contains the double copy of original array
var auxiliary: Array[Int] = Array.fill[Int](n * 2)(0);
var i: Int = 0;
while (i < n)
{
auxiliary(i) = arr(i);
// Append similar element at the end
auxiliary(i + n) = arr(i);
i += 1;
}
i = 0;
while (i < n)
{
result = maxValue(result,
longestIncSubsequences(auxiliary, i, i + n));
i += 1;
}
// Display given array
printElement(arr, n);
// Display calculated result
println("\n Length of CLIS 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(7, 8, 6, 9, 4, 5, 6);
var arr2: Array[Int] = Array(7, 9, 3, 4, 8, 7, 2);
var arr3: Array[Int] = Array(12, 11, 10, 7, 8, 1, 2, 9, 3);
// Test A
// [ 7, 8, 6, 9, 4 , 5, 6]
// length of Longest circular increasing subsequence 6
// (4 , 5, 6, 7, 8, 9)
// Result = 6
var n: Int = arr1.length;
task.findCireculLISS(arr1, n);
// Test B
// arr = [ 7 , 9 , 3 , 4 , 8 , 7 , 2]
// length of Longest circular increasing subsequence 4
// (3, 4, 7 , 9), (3 , 4 , 8, 9) etc
// Result = 4
n = arr2.length;
task.findCireculLISS(arr2, n);
// Test C
// arr = [ 12 11 10 7 8 1 2 9 3]
// [1, 2, 3, 7, 8]
// Result : 5
n = arr3.length;
task.findCireculLISS(arr3, n);
}
}
Output
7 8 6 9 4 5 6
Length of CLIS is : 6
7 9 3 4 8 7 2
Length of CLIS is : 4
12 11 10 7 8 1 2 9 3
Length of CLIS is : 5
import Foundation;
// Swift 4 program for
// Find circular 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 maxValue(_ a: Int, _ b: Int) -> Int
{
if (a > b)
{
return a;
}
return b;
}
func longestIncSubsequences(_ arr: [Int], _ s: Int, _ e: Int) -> Int
{
// Define auxiliary list
// Set initial 1 length of each element
var length: [Int] = Array(repeating: 1, count: e);
// Define some auxiliary variables
var i: Int = s + 1;
var j: Int = 0;
var ans: Int = 1;
// Execute loop through by size of array
while (i < e)
{
j = s;
// 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] > ans)
{
ans = length[i];
}
}
}
j += 1;
}
i += 1;
}
return ans;
}
// Handles the request to finding circular increasing subsequence
func findCireculLISS(_ arr: [Int], _ n: Int)
{
if (n <= 0)
{
return;
}
var result: Int = 0;
// Auxiliary array which contains the double copy of original array
var auxiliary: [Int] = Array(repeating: 0, count: n * 2);
var i: Int = 0;
while (i < n)
{
auxiliary[i] = arr[i];
// Append similar element at the end
auxiliary[i + n] = arr[i];
i += 1;
}
i = 0;
while (i < n)
{
result = self.maxValue(result,
self.longestIncSubsequences(auxiliary, i, i + n));
i += 1;
}
// Display given array
self.printElement(arr, n);
// Display calculated result
print("\n Length of CLIS is : ", result);
}
}
func main()
{
let task: Subsequence = Subsequence();
// Define array of integer elements
let arr1: [Int] = [7, 8, 6, 9, 4, 5, 6];
let arr2: [Int] = [7, 9, 3, 4, 8, 7, 2];
let arr3: [Int] = [12, 11, 10, 7, 8, 1, 2, 9, 3];
// Test A
// [ 7, 8, 6, 9, 4 , 5, 6]
// length of Longest circular increasing subsequence 6
// (4 , 5, 6, 7, 8, 9)
// Result = 6
var n: Int = arr1.count;
task.findCireculLISS(arr1, n);
// Test B
// arr = [ 7 , 9 , 3 , 4 , 8 , 7 , 2]
// length of Longest circular increasing subsequence 4
// (3, 4, 7 , 9), (3 , 4 , 8, 9) etc
// Result = 4
n = arr2.count;
task.findCireculLISS(arr2, n);
// Test C
// arr = [ 12 11 10 7 8 1 2 9 3]
// [1, 2, 3, 7, 8]
// Result : 5
n = arr3.count;
task.findCireculLISS(arr3, n);
}
main();
Output
7 8 6 9 4 5 6
Length of CLIS is : 6
7 9 3 4 8 7 2
Length of CLIS is : 4
12 11 10 7 8 1 2 9 3
Length of CLIS is : 5
// Kotlin program for
// Find circular 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 maxValue(a: Int, b: Int): Int
{
if (a > b)
{
return a;
}
return b;
}
fun longestIncSubsequences(arr: Array < Int > , s: Int, e: Int): Int
{
// Define auxiliary list
// Set initial 1 length of each element
val length: Array < Int > = Array(e)
{
1
};
// Define some auxiliary variables
var i: Int = s + 1;
var j: Int;
var ans: Int = 1;
// Execute loop through by size of array
while (i < e)
{
j = s;
// 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] > ans)
{
ans = length[i];
}
}
}
j += 1;
}
i += 1;
}
return ans;
}
// Handles the request to finding circular increasing subsequence
fun findCireculLISS(arr: Array < Int > , n: Int): Unit
{
if (n <= 0)
{
return;
}
var result: Int = 0;
// Auxiliary array which contains the double copy of original array
val auxiliary: Array < Int > = Array(n * 2)
{
1
};
var i: Int = 0;
while (i < n)
{
auxiliary[i] = arr[i];
// Append similar element at the end
auxiliary[i + n] = arr[i];
i += 1;
}
i = 0;
while (i < n)
{
result = this.maxValue(result,
this.longestIncSubsequences(
auxiliary, i, i + n));
i += 1;
}
// Display given array
this.printElement(arr, n);
// Display calculated result
println("\n Length of CLIS is : " + result);
}
}
fun main(args: Array < String > ): Unit
{
val task: Subsequence = Subsequence();
// Define array of integer elements
val arr1: Array < Int > = arrayOf(7, 8, 6, 9, 4, 5, 6);
val arr2: Array < Int > = arrayOf(7, 9, 3, 4, 8, 7, 2);
val arr3: Array < Int > = arrayOf(12, 11, 10, 7, 8, 1, 2, 9, 3);
// Test A
// [ 7, 8, 6, 9, 4 , 5, 6]
// length of Longest circular increasing subsequence 6
// (4 , 5, 6, 7, 8, 9)
// Result = 6
var n: Int = arr1.count();
task.findCireculLISS(arr1, n);
// Test B
// arr = [ 7 , 9 , 3 , 4 , 8 , 7 , 2]
// length of Longest circular increasing subsequence 4
// (3, 4, 7 , 9), (3 , 4 , 8, 9) etc
// Result = 4
n = arr2.count();
task.findCireculLISS(arr2, n);
// Test C
// arr = [ 12 11 10 7 8 1 2 9 3]
// [1, 2, 3, 7, 8]
// Result : 5
n = arr3.count();
task.findCireculLISS(arr3, n);
}
Output
7 8 6 9 4 5 6
Length of CLIS is : 6
7 9 3 4 8 7 2
Length of CLIS is : 4
12 11 10 7 8 1 2 9 3
Length of CLIS is : 5
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