Dada una array, la tarea es encontrar LIS (Subsecuencia creciente más larga) de forma circular.
Ejemplos:
Input : arr[] = {5, 4, 3, 2, 1}
Output : 2
Although there is no LIS in a given array
but in a circular form there can be
{1, 5}, {2, 5}, ......
Input : arr[]= {5, 6, 7, 1, 2, 3}
Output : 6
{1, 2, 3, 5, 6, 7} will be the LIS in the
circular manner.
- Agregue los mismos elementos (es decir, toda la array) con la array dada.
- Para cada ventana de tamaño n (número de elementos en la array dada), realice LIS.
- Devuelve la longitud máxima.
For example : Given array is {1, 4, 6, 2, 3}
After appending elements resultant array
will be {1, 4, 6, 2, 3, 1, 4, 6, 2, 3}.
Now for every consecutive n elements perform LIS.
1- {1, 4, 6, 2, 3} --3 is length of LIS.
2- {4, 6, 2, 3, 1} --2 is length of LIS.
3- {6, 2, 3, 1, 4} --3
4- {2, 3, 1, 4, 6}-- 4 {2, 3, 4, 6}
5- {3, 1, 4, 6, 2} --3.
6- {1, 4, 6, 2, 3} Original list.
So, maximum length of LIS in circular manner is 4.
Como en la última ventana, tendremos los mismos elementos que en la array dada que no necesitamos calcular nuevamente, por lo que podemos agregar solo n-1 elementos para reducir la cantidad de operaciones.
C++
// C++ implementation to find LIS in circular way
#include<bits/stdc++.h>
using namespace std;
// Utility function to find LIS using Dynamic programming
int computeLIS(int circBuff[], int start, int end, int n)
{
int LIS[end-start];
/* Initialize LIS values for all indexes */
for (int i = start; i < end; i++)
LIS[i] = 1;
/* Compute optimized LIS values in bottom up manner */
for (int i = start + 1; i < end; i++)
// Set j on the basis of current window
// i.e. first element of the current window
for (int j = start; j < i; j++ )
if (circBuff[i] > circBuff[j] && LIS[i] < LIS[j] + 1)
LIS[i] = LIS[j] + 1;
/* Pick maximum of all LIS values */
int res = INT_MIN;
for (int i = start; i < end; i++)
res = max(res, LIS[i]);
return res;
}
// Function to find Longest Increasing subsequence in
// Circular manner
int LICS(int arr[], int n)
{
// Make a copy of given array by appending same
// array elements to itself
int circBuff[2 * n];
for (int i = 0; i<n; i++)
circBuff[i] = arr[i];
for (int i = n; i < 2*n; i++)
circBuff[i] = arr[i-n];
// Perform LIS for each window of size n
int res = INT_MIN;
for (int i=0; i<n; i++)
res = max(computeLIS(circBuff, i, i + n, n), res);
return res;
}
/* Driver program to test above function */
int main()
{
int arr[] = { 1, 4, 6, 2, 3 };
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Length of LICS is " << LICS( arr, n );
return 0;
}
Java
// Java implementation to find LIS in circular way
class Test
{
// Utility method to find LIS using Dynamic programming
static int computeLIS(int circBuff[], int start, int end, int n)
{
int LIS[] = new int[n+end-start];
/* Initialize LIS values for all indexes */
for (int i = start; i < end; i++)
LIS[i] = 1;
/* Compute optimized LIS values in bottom up manner */
for (int i = start + 1; i < end; i++)
// Set j on the basis of current window
// i.e. first element of the current window
for (int j = start; j < i; j++ )
if (circBuff[i] > circBuff[j] && LIS[i] < LIS[j] + 1)
LIS[i] = LIS[j] + 1;
/* Pick maximum of all LIS values */
int res = Integer.MIN_VALUE;
for (int i = start; i < end; i++)
res = Math.max(res, LIS[i]);
return res;
}
// Function to find Longest Increasing subsequence in
// Circular manner
static int LICS(int arr[], int n)
{
// Make a copy of given array by appending same
// array elements to itself
int circBuff[] = new int[2 * n];
for (int i = 0; i<n; i++)
circBuff[i] = arr[i];
for (int i = n; i < 2*n; i++)
circBuff[i] = arr[i-n];
// Perform LIS for each window of size n
int res = Integer.MIN_VALUE;
for (int i=0; i<n; i++)
res = Math.max(computeLIS(circBuff, i, i + n, n), res);
return res;
}
// Driver method
public static void main(String args[])
{
int arr[] = { 1, 4, 6, 2, 3 };
System.out.println("Length of LICS is " + LICS( arr, arr.length));
}
}
Python3
# Python3 implementation to find
# LIS in circular way Utility
# function to find LIS using
# Dynamic programmi
def computeLIS(circBuff, start, end, n):
LIS = [0 for i in range(end)]
# Initialize LIS values
# for all indexes
for i in range(start, end):
LIS[i] = 1
# Compute optimized LIS values
# in bottom up manner
for i in range(start + 1, end):
# Set j on the basis of current
# window i.e. first element of
# the current window
for j in range(start,i):
if (circBuff[i] > circBuff[j] and
LIS[i] < LIS[j] + 1):
LIS[i] = LIS[j] + 1
# Pick maximum of all LIS values
res = -100000
for i in range(start, end):
res = max(res, LIS[i])
return res
# Function to find Longest Increasing
# subsequence in Circular manner
def LICS(arr, n):
# Make a copy of given
# array by appending same
# array elements to itself
circBuff = [0 for i in range(2 * n)]
for i in range(n):
circBuff[i] = arr[i]
for i in range(n, 2 * n):
circBuff[i] = arr[i - n]
# Perform LIS for each
# window of size n
res = -100000
for i in range(n):
res = max(computeLIS(circBuff, i,
i + n, n), res)
return res
# Driver code
arr = [ 1, 4, 6, 2, 3 ]
n = len(arr)
print("Length of LICS is", LICS(arr, n))
# This code is contributed
# by sahilshelangia
C#
// C# implementation to find
// LIS in circular way
using System;
class Test
{
// Utility method to find LIS
// using Dynamic programming
static int computeLIS(int []circBuff, int start,
int end, int n)
{
int []LIS = new int[n+end-start];
/* Initialize LIS values for all indexes */
for (int i = start; i < end; i++)
LIS[i] = 1;
/* Compute optimized LIS values
in bottom up manner */
for (int i = start + 1; i < end; i++)
// Set j on the basis of current window
// i.e. first element of the current window
for (int j = start; j < i; j++ )
if (circBuff[i] > circBuff[j] &&
LIS[i] < LIS[j] + 1)
LIS[i] = LIS[j] + 1;
/* Pick maximum of all LIS values */
int res = int.MinValue;
for (int i = start; i < end; i++)
res = Math.Max(res, LIS[i]);
return res;
}
// Function to find Longest Increasing
// subsequence in Circular manner
static int LICS(int []arr, int n)
{
// Make a copy of given array by
// appending same array elements to itself
int []circBuff = new int[2 * n];
for (int i = 0; i<n; i++)
circBuff[i] = arr[i];
for (int i = n; i < 2*n; i++)
circBuff[i] = arr[i-n];
// Perform LIS for each window of size n
int res = int.MinValue;
for (int i=0; i<n; i++)
res = Math.Max(computeLIS(circBuff, i, i + n, n), res);
return res;
}
// Driver method
public static void Main()
{
int []arr = {1, 4, 6, 2, 3};
Console.Write("Length of LICS is " +
LICS( arr, arr.Length));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP implementation to
// find LIS in circular way
// Utility function to find
// LIS using Dynamic programming
function computeLIS($circBuff,
$start,
$end, $n)
{
$LIS = Array();
/* Initialize LIS values
for all indexes */
for ($i = $start; $i < $end; $i++)
$LIS[$i] = 1;
/* Compute optimized LIS
values in bottom up manner */
for ($i = $start + 1; $i < $end; $i++)
// Set j on the basis of
// current window
// i.e. first element of
// the current window
for ( $j = $start; $j < $i; $j++ )
if ($circBuff[$i] > $circBuff[$j] &&
$LIS[$i] < $LIS[$j] + 1)
$LIS[$i] = $LIS[$j] + 1;
/* Pick maximum of
all LIS values */
$res = PHP_INT_MIN;
for ($i = $start; $i < $end; $i++)
$res = max($res, $LIS[$i]);
return $res;
}
// Function to find LIS
// in Circular manner
function LICS($arr, $n)
{
// Make a copy of given array
// by appending same array
// elements to itself
for ($i = 0; $i < $n; $i++)
$circBuff[$i] = $arr[$i];
for ($i = $n; $i < 2 * $n; $i++)
$circBuff[$i] = $arr[$i - $n];
// Perform LIS for each
// window of size n
$res = PHP_INT_MIN;
for ($i = 0; $i < $n; $i++)
$res = max(computeLIS($circBuff, $i,
$i + $n, $n),
$res);
return $res;
}
// Driver Code
$arr = array(1, 4, 6, 2, 3);
$n = sizeof($arr);
echo "Length of LICS is " ,
LICS($arr, $n);
// This code is contributed by aj_36
?>
Javascript
<script>
// Javascript implementation to find LIS in circular way
// Utility method to find LIS
// using Dynamic programming
function computeLIS(circBuff, start, end, n)
{
let LIS = new Array(n+end-start);
/* Initialize LIS values for all indexes */
for (let i = start; i < end; i++)
LIS[i] = 1;
/* Compute optimized LIS values
in bottom up manner */
for (let i = start + 1; i < end; i++)
// Set j on the basis of current window
// i.e. first element of the current window
for (let j = start; j < i; j++ )
if (circBuff[i] > circBuff[j] && LIS[i] < LIS[j] + 1)
LIS[i] = LIS[j] + 1;
/* Pick maximum of all LIS values */
let res = Number.MIN_VALUE;
for (let i = start; i < end; i++)
res = Math.max(res, LIS[i]);
return res;
}
// Function to find Longest Increasing
// subsequence in Circular manner
function LICS(arr, n)
{
// Make a copy of given array by
// appending same array elements to itself
let circBuff = new Array(2 * n);
for (let i = 0; i<n; i++)
circBuff[i] = arr[i];
for (let i = n; i < 2*n; i++)
circBuff[i] = arr[i-n];
// Perform LIS for each window of size n
let res = Number.MIN_VALUE;
for (let i=0; i<n; i++)
res = Math.max(computeLIS(circBuff, i, i + n, n), res);
return res;
}
let arr = [1, 4, 6, 2, 3];
document.write("Length of LICS is " + LICS( arr, arr.length));
</script>
Producción :
Length of LICS is 4
La complejidad temporal de la solución anterior es O(n 3 ). Se puede reducir O(n 2 Log n) usando el algoritmo O(n Log n) para encontrar LIS .
Referencia:
https://www.careercup.com/question?id=5942735794077696
Este artículo es una contribución de Sahil Chhabra . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA