Dado un arreglo A[0 … n-1] que contiene n enteros positivos, un subarreglo A[i … j] es bitónico si existe un ak con i <= k <= j tal que A[i] <= A[i + 1] … = A[k + 1] >= .. A[j – 1] > = A[j]. Escriba una función que tome una array como argumento y devuelva la longitud del subarreglo bitónico de longitud máxima.
La complejidad temporal esperada de la solución es O(n)
Ejemplos simples
1) A[] = {12, 4, 78, 90, 45, 23}, la longitud máxima del subarreglo bitónico es {4, 78, 90, 45, 23} que es de longitud 5.
2) A[] = {20, 4, 1, 2, 3, 4, 2, 10}, el subarreglo bitónico de longitud máxima es {1, 2, 3, 4, 2} que es de longitud 5.
Ejemplos extremos
1) A[] = {10}, el elemento único es bitónico, por lo que la salida es 1.
2)A[] = {10, 20, 30, 40}, la array completa en sí es bitónica, por lo que la salida es 4.
3) A[] = {40, 30, 20, 10}, la array completa en sí es bitónica, por lo que la salida es 4
Solución
Consideremos el arreglo {12, 4, 78, 90, 45, 23} para entender la solución.
1) Construya un arreglo auxiliar inc[] de izquierda a derecha tal que inc[i] contenga la longitud del subarreglo no decreciente que termina en arr[i].
Para A[] = {12, 4, 78, 90, 45, 23}, inc[] es {1, 1, 2, 3, 1, 1}
2) Construya otra array dec[] de derecha a izquierda tal que dec[i] contiene la longitud del subarreglo no creciente que comienza en arr[i].
Para A[] = {12, 4, 78, 90, 45, 23}, dec[] es {2, 1, 1, 3, 2, 1}.
3) Una vez que tenemos las arrays inc[] y dec[], todo lo que necesitamos hacer es encontrar el valor máximo de (inc[i] + dec[i] – 1).
Para {12, 4, 78, 90, 45, 23}, el valor máximo de (inc[i] + dec[i] – 1) es 5 para i = 3.
C++
// C++ program to find length of
// the longest bitonic subarray
#include <bits/stdc++.h>
using namespace std;
int bitonic(int arr[], int n)
{
// Length of increasing subarray
// ending at all indexes
int inc[n];
// Length of decreasing subarray
// starting at all indexes
int dec[n];
int i, max;
// length of increasing sequence
// ending at first index is 1
inc[0] = 1;
// length of increasing sequence
// starting at first index is 1
dec[n-1] = 1;
// Step 1) Construct increasing sequence array
for (i = 1; i < n; i++)
inc[i] = (arr[i] >= arr[i-1])? inc[i-1] + 1: 1;
// Step 2) Construct decreasing sequence array
for (i = n-2; i >= 0; i--)
dec[i] = (arr[i] >= arr[i+1])? dec[i+1] + 1: 1;
// Step 3) Find the length of
// maximum length bitonic sequence
max = inc[0] + dec[0] - 1;
for (i = 1; i < n; i++)
if (inc[i] + dec[i] - 1 > max)
max = inc[i] + dec[i] - 1;
return max;
}
/* Driver code */
int main()
{
int arr[] = {12, 4, 78, 90, 45, 23};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "nLength of max length Bitonic Subarray is " << bitonic(arr, n);
return 0;
}
// This is code is contributed by rathbhupendra
C
// C program to find length of the longest bitonic subarray
#include<stdio.h>
#include<stdlib.h>
int bitonic(int arr[], int n)
{
int inc[n]; // Length of increasing subarray ending at all indexes
int dec[n]; // Length of decreasing subarray starting at all indexes
int i, max;
// length of increasing sequence ending at first index is 1
inc[0] = 1;
// length of increasing sequence starting at first index is 1
dec[n-1] = 1;
// Step 1) Construct increasing sequence array
for (i = 1; i < n; i++)
inc[i] = (arr[i] >= arr[i-1])? inc[i-1] + 1: 1;
// Step 2) Construct decreasing sequence array
for (i = n-2; i >= 0; i--)
dec[i] = (arr[i] >= arr[i+1])? dec[i+1] + 1: 1;
// Step 3) Find the length of maximum length bitonic sequence
max = inc[0] + dec[0] - 1;
for (i = 1; i < n; i++)
if (inc[i] + dec[i] - 1 > max)
max = inc[i] + dec[i] - 1;
return max;
}
/* Driver program to test above function */
int main()
{
int arr[] = {12, 4, 78, 90, 45, 23};
int n = sizeof(arr)/sizeof(arr[0]);
printf("nLength of max length Bitonic Subarray is %d",
bitonic(arr, n));
return 0;
}
Java
// Java program to find length of the longest bitonic subarray
import java.io.*;
import java.util.*;
class Bitonic
{
static int bitonic(int arr[], int n)
{
int[] inc = new int[n]; // Length of increasing subarray ending
// at all indexes
int[] dec = new int[n]; // Length of decreasing subarray starting
// at all indexes
int max;
// Length of increasing sequence ending at first index is 1
inc[0] = 1;
// Length of increasing sequence starting at first index is 1
dec[n-1] = 1;
// Step 1) Construct increasing sequence array
for (int i = 1; i < n; i++)
inc[i] = (arr[i] >= arr[i-1])? inc[i-1] + 1: 1;
// Step 2) Construct decreasing sequence array
for (int i = n-2; i >= 0; i--)
dec[i] = (arr[i] >= arr[i+1])? dec[i+1] + 1: 1;
// Step 3) Find the length of maximum length bitonic sequence
max = inc[0] + dec[0] - 1;
for (int i = 1; i < n; i++)
if (inc[i] + dec[i] - 1 > max)
max = inc[i] + dec[i] - 1;
return max;
}
/*Driver function to check for above function*/
public static void main (String[] args)
{
int arr[] = {12, 4, 78, 90, 45, 23};
int n = arr.length;
System.out.println("Length of max length Bitnoic Subarray is "
+ bitonic(arr, n));
}
}
/* This code is contributed by Devesh Agrawal */
Python3
# Python program to find length of the longest bitonic subarray
def bitonic(arr, n):
# Length of increasing subarray ending at all indexes
inc = [None] * n
# Length of decreasing subarray starting at all indexes
dec = [None] * n
# length of increasing sequence ending at first index is 1
inc[0] = 1
# length of increasing sequence starting at first index is 1
dec[n-1] = 1
# Step 1) Construct increasing sequence array
for i in range(n):
if arr[i] >= arr[i-1]:
inc[i] = inc[i-1] + 1
else:
inc[i] = 1
# Step 2) Construct decreasing sequence array
for i in range(n-2,-1,-1):
if arr[i] >= arr[i-1]:
dec[i] = inc[i-1] + 1
else:
dec[i] = 1
# Step 3) Find the length of maximum length bitonic sequence
max = inc[0] + dec[0] - 1
for i in range(n):
if inc[i] + dec[i] - 1 > max:
max = inc[i] + dec[i] - 1
return max
# Driver program to test above function
arr = [12, 4, 78, 90, 45, 23]
n = len(arr)
print("nLength of max length Bitonic Subarray is ",bitonic(arr, n))
C#
// C# program to find length of the
// longest bitonic subarray
using System;
class GFG
{
static int bitonic(int []arr, int n)
{
// Length of increasing subarray ending
// at all indexes
int[] inc = new int[n];
// Length of decreasing subarray starting
// at all indexes
int[] dec = new int[n];
int max;
// Length of increasing sequence
// ending at first index is 1
inc[0] = 1;
// Length of increasing sequence
// starting at first index is 1
dec[n - 1] = 1;
// Step 1) Construct increasing sequence array
for (int i = 1; i < n; i++)
inc[i] = (arr[i] >= arr[i - 1]) ?
inc[i - 1] + 1: 1;
// Step 2) Construct decreasing sequence array
for (int i = n - 2; i >= 0; i--)
dec[i] = (arr[i] >= arr[i + 1]) ?
dec[i + 1] + 1: 1;
// Step 3) Find the length of maximum
// length bitonic sequence
max = inc[0] + dec[0] - 1;
for (int i = 1; i < n; i++)
if (inc[i] + dec[i] - 1 > max)
max = inc[i] + dec[i] - 1;
return max;
}
// Driver function
public static void Main ()
{
int []arr = {12, 4, 78, 90, 45, 23};
int n = arr.Length;
Console.Write("Length of max length Bitonic Subarray is "
+ bitonic(arr, n));
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP program to find length of
// the longest bitonic subarray
function bitonic($arr, $n)
{
$i; $max;
// length of increasing sequence
// ending at first index is 1
$inc[0] = 1;
// length of increasing sequence
// starting at first index is 1
$dec[$n - 1] = 1;
// Step 1) Construct increasing
// sequence array
for ($i = 1; $i < $n; $i++)
$inc[$i] = ($arr[$i] >= $arr[$i - 1]) ?
$inc[$i - 1] + 1: 1;
// Step 2) Construct decreasing
// sequence array
for ($i = $n - 2; $i >= 0; $i--)
$dec[$i] = ($arr[$i] >= $arr[$i + 1]) ?
$dec[$i + 1] + 1: 1;
// Step 3) Find the length of
// maximum length bitonic sequence
$max = $inc[0] + $dec[0] - 1;
for ($i = 1; $i < $n; $i++)
if ($inc[$i] + $dec[$i] - 1 > $max)
$max = $inc[$i] + $dec[$i] - 1;
return $max;
}
// Driver Code
$arr = array(12, 4, 78, 90, 45, 23);
$n = sizeof($arr);
echo "Length of max length Bitonic " .
"Subarray is ", bitonic($arr, $n);
// This code is contributed by aj_36
?>
Javascript
<script>
// Javascript program to find length of the
// longest bitonic subarray
function bitonic(arr, n)
{
// Length of increasing subarray ending
// at all indexes
let inc = new Array(n);
// Length of decreasing subarray starting
// at all indexes
let dec = new Array(n);
let max;
// Length of increasing sequence
// ending at first index is 1
inc[0] = 1;
// Length of increasing sequence
// starting at first index is 1
dec[n - 1] = 1;
// Step 1) Construct increasing sequence array
for (let i = 1; i < n; i++)
inc[i] = (arr[i] >= arr[i - 1]) ? inc[i - 1] + 1: 1;
// Step 2) Construct decreasing sequence array
for (let i = n - 2; i >= 0; i--)
dec[i] = (arr[i] >= arr[i + 1]) ? dec[i + 1] + 1: 1;
// Step 3) Find the length of maximum
// length bitonic sequence
max = inc[0] + dec[0] - 1;
for (let i = 1; i < n; i++)
if (inc[i] + dec[i] - 1 > max)
max = inc[i] + dec[i] - 1;
return max;
}
let arr = [12, 4, 78, 90, 45, 23];
let n = arr.length;
document.write("Length of max length Bitonic Subarray is " + bitonic(arr, n));
</script>
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