Dada una array que contiene n números. El problema es encontrar la longitud del subarreglo contiguo más largo de manera circular, de modo que cada elemento del subarreglo sea estrictamente mayor que su elemento anterior en el mismo subarreglo. La complejidad del tiempo debe ser O(n).
Ejemplos:
Input : arr[] = {2, 3, 4, 5, 1}
Output : 5
{2, 3, 4, 5, 1} is the subarray if we circularly
start from the last element and then take the
first four elements. This will give us an increasing
subarray {1, 2, 3, 4, 5} in a circular manner.
Input : arr[] = {2, 3, 8, 4, 6, 7, 10, 12, 9, 1}
Output : 5
Método 1 (usando espacio adicional): haga una array temp[] de tamaño 2*n. Copie los elementos de arr[] en temp[] dos veces. Ahora, encuentre la longitud del subarreglo creciente más largo en temp[].
Método 2 (sin usar espacio extra):
Los siguientes son los pasos:
- Si n == 1, devuelve 1.
- Encuentre la longitud del subarreglo creciente más largo comenzando con el primer elemento de arr[]. Sea su longitud startLen .
- Comenzando desde el siguiente elemento donde termina el primer subarreglo creciente, encuentre la longitud del subarreglo creciente más largo . Que sea máximo .
- Considere la longitud del subarreglo creciente que termina con el último elemento de arr[]. Que se acabeLen .
- Si arr[n-1] < arr[0], entonces endLen = endLen + startLen.
- Finalmente, devuelva el máximo de (max, endLen, startLen).
Implementación:
C++
// C++ implementation to find length of longest
// increasing circular subarray
#include <bits/stdc++.h>
using namespace std;
// function to find length of longest
// increasing circular subarray
int longlenCircularSubarr(int arr[], int n)
{
// if there is only one element
if (n == 1)
return 1;
// 'startLen' stores the length of the longest
// increasing subarray which starts from
// first element
int startLen = 1, i;
int len = 1, max = 0;
// finding the length of the longest
// increasing subarray starting from
// first element
for (i = 1; i < n; i++) {
if (arr[i - 1] < arr[i])
startLen++;
else
break;
}
if (max < startLen)
max = startLen;
// traverse the array index (i+1)
for (int j = i + 1; j < n; j++) {
// if current element if greater than previous
// element, then this element helps in building
// up the previous increasing subarray encountered
// so far
if (arr[j - 1] < arr[j])
len++;
else {
// check if 'max' length is less than the length
// of the current increasing subarray. If true,
// then update 'max'
if (max < len)
max = len;
// reset 'len' to 1 as from this element
// again the length of the new increasing
// subarray is being calculated
len = 1;
}
}
// if true, then add length of the increasing
// subarray ending at last element with the
// length of the increasing subarray starting
// from first element - This is done for
// circular rotation
if (arr[n - 1] < arr[0])
len += startLen;
// check if 'max' length is less than the length
// of the current increasing subarray. If true,
// then update 'max'
if (max < len)
max = len;
return max;
}
// Driver program to test above
int main()
{
int arr[] = { 2, 3, 4, 5, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Length = "
<< longlenCircularSubarr(arr, n);
return 0;
}
Java
// Java implementation to find length
// of longest increasing circular subarray
class Circular
{
// function to find length of longest
// increasing circular subarray
public static int longlenCircularSubarr(int arr[],
int n)
{
// if there is only one element
if (n == 1)
return 1;
// 'startLen' stores the length of the
// longest increasing subarray which
// starts from first element
int startLen = 1, i;
int len = 1, max = 0;
// finding the length of the longest
// increasing subarray starting from
// first element
for (i = 1; i < n; i++) {
if (arr[i - 1] < arr[i])
startLen++;
else
break;
}
if (max < startLen)
max = startLen;
// traverse the array index (i+1)
for (int j = i + 1; j < n; j++) {
// if current element if greater than
// previous element, then this element
// helps in building up the previous
// increasing subarray encountered so far
if (arr[j - 1] < arr[j])
len++;
else {
// check if 'max' length is less than
// the length of the current increasing
// subarray. If true, then update 'max'
if (max < len)
max = len;
// reset 'len' to 1 as from this element
// again the length of the new increasing
// subarray is being calculated
len = 1;
}
}
// if true, then add length of the increasing
// subarray ending at last element with the
// length of the increasing subarray starting
// from first element - This is done for
// circular rotation
if (arr[n - 1] < arr[0])
len += startLen;
// check if 'max' length is less than the
// length of the current increasing subarray.
// If true, then update 'max'
if (max < len)
max = len;
return max;
}
// driver code
public static void main(String[] args)
{
int arr[] = { 2, 3, 4, 5, 1 };
int n = 5;
System.out.print("Length = "+
longlenCircularSubarr(arr, n));
}
}
// This code is contributed by rishabh_jain
Python3
# Python3 implementation to find length
# of longest increasing circular subarray
# function to find length of longest
# increasing circular subarray
def longlenCircularSubarr (arr, n):
# if there is only one element
if n == 1:
return 1
# 'startLen' stores the length of the
# longest increasing subarray which
# starts from first element
startLen = 1
len = 1
max = 0
# finding the length of the longest
# increasing subarray starting from
# first element
for i in range(1, n):
if arr[i - 1] < arr[i]:
startLen+=1
else:
break
if max < startLen:
max = startLen
# traverse the array index (i+1)
for j in range(i + 1, n):
# if current element if greater than
# previous element, then this element
# helps in building up the previous
# increasing subarray encountered
# so far
if arr[j - 1] < arr[j]:
len+=1
else:
# check if 'max' length is less
# than the length of the current
# increasing subarray. If true,
# then update 'max'
if max < len:
max = len
# reset 'len' to 1 as from this
# element again the length of the
# new increasing subarray is
# being calculated
len = 1
# if true, then add length of the increasing
# subarray ending at last element with the
# length of the increasing subarray starting
# from first element - This is done for
# circular rotation
if arr[n - 1] < arr[0]:
len += startLen
# check if 'max' length is less than the
# length of the current increasing subarray.
# If true, then update 'max'
if max < len:
max = len
return max
# Driver code to test above
arr = [ 2, 3, 4, 5, 1 ]
n = len(arr)
print("Length = ",longlenCircularSubarr(arr, n))
# This code is contributed by "Sharad_Bhardwaj".
C#
// C# implementation to find length
// of longest increasing circular subarray
using System;
public class GFG {
// function to find length of longest
// increasing circular subarray
static int longlenCircularSubarr(int[] arr, int n)
{
// if there is only one element
if (n == 1)
return 1;
// 'startLen' stores the length of the longest
// increasing subarray which starts from
// first element
int startLen = 1, i;
int len = 1, max = 0;
// finding the length of the longest
// increasing subarray starting from
// first element
for (i = 1; i < n; i++) {
if (arr[i - 1] < arr[i])
startLen++;
else
break;
}
if (max < startLen)
max = startLen;
// traverse the array index (i+1)
for (int j = i + 1; j < n; j++) {
// if current element if greater than previous
// element, then this element helps in building
// up the previous increasing subarray encountered
// so far
if (arr[j - 1] < arr[j])
len++;
else {
// check if 'max' length is less than the length
// of the current increasing subarray. If true,
// then update 'max'
if (max < len)
max = len;
// reset 'len' to 1 as from this element
// again the length of the new increasing
// subarray is being calculated
len = 1;
}
}
// if true, then add length of the increasing
// subarray ending at last element with the
// length of the increasing subarray starting
// from first element - This is done for
// circular rotation
if (arr[n - 1] < arr[0])
len += startLen;
// check if 'max' length is less than the length
// of the current increasing subarray. If true,
// then update 'max'
if (max < len)
max = len;
return max;
}
// Driver program to test above
static public void Main()
{
int[] arr = { 2, 3, 4, 5, 1 };
int n = arr.Length;
Console.WriteLine("Length = " +
longlenCircularSubarr(arr, n));
// Code
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP implementation to find length of longest
// increasing circular subarray
// function to find length of longest
// increasing circular subarray
function longlenCircularSubarr(&$arr, $n)
{
// if there is only one element
if ($n == 1)
return 1;
// 'startLen' stores the length of the longest
// increasing subarray which starts from
// first element
$startLen = 1;
$len = 1;
$max = 0;
// finding the length of the longest
// increasing subarray starting from
// first element
for ($i = 1; $i < $n; $i++)
{
if ($arr[$i - 1] < $arr[$i])
$startLen++;
else
break;
}
if ($max < $startLen)
$max = $startLen;
// traverse the array index (i+1)
for ($j = $i + 1; $j < $n; $j++)
{
// if current element if greater than
// previous element, then this element
// helps in building up the previous
// increasing subarray encountered
// so far
if ($arr[$j - 1] < $arr[$j])
$len++;
else
{
// check if 'max' length is less than
// the length of the current increasing
// subarray. If true, then update 'max'
if ($max < $len)
$max = $len;
// reset 'len' to 1 as from this element
// again the length of the new increasing
// subarray is being calculated
$len = 1;
}
}
// if true, then add length of the increasing
// subarray ending at last element with the
// length of the increasing subarray starting
// from first element - This is done for
// circular rotation
if ($arr[$n - 1] < $arr[0])
$len += $startLen;
// check if 'max' length is less than the length
// of the current increasing subarray. If true,
// then update 'max'
if ($max < $len)
$max = $len;
return $max;
}
// Driver Code
$arr = array( 2, 3, 4, 5, 1 );
$n = sizeof($arr);
echo "Length = " . longlenCircularSubarr($arr, $n);
// This code is contributed by ita_c
?>
Javascript
<script>
// Javascript implementation to find length
// of longest increasing circular subarray
// function to find length of longest
// increasing circular subarray
function longlenCircularSubarr(arr,n)
{
// if there is only one element
if (n == 1)
return 1;
// 'startLen' stores the length of the
// longest increasing subarray which
// starts from first element
let startLen = 1, i;
let len = 1, max = 0;
// finding the length of the longest
// increasing subarray starting from
// first element
for (i = 1; i < n; i++) {
if (arr[i - 1] < arr[i])
startLen++;
else
break;
}
if (max < startLen)
max = startLen;
// traverse the array index (i+1)
for (let j = i + 1; j < n; j++) {
// if current element if greater than
// previous element, then this element
// helps in building up the previous
// increasing subarray encountered so far
if (arr[j - 1] < arr[j])
len++;
else {
// check if 'max' length is less than
// the length of the current increasing
// subarray. If true, then update 'max'
if (max < len)
max = len;
// reset 'len' to 1 as from this element
// again the length of the new increasing
// subarray is being calculated
len = 1;
}
}
// if true, then add length of the increasing
// subarray ending at last element with the
// length of the increasing subarray starting
// from first element - This is done for
// circular rotation
if (arr[n - 1] < arr[0])
len += startLen;
// check if 'max' length is less than the
// length of the current increasing subarray.
// If true, then update 'max'
if (max < len)
max = len;
return max;
}
// driver code
let arr=[2, 3, 4, 5, 1 ];
let n = 5;
document.write("Length = "+
longlenCircularSubarr(arr, n));
// This code is contributed by avanitrachhadiya2155
</script>
Producción
Length = 5
Complejidad temporal: O(n).
Publicación traducida automáticamente
Artículo escrito por ayushjauhari14 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA