Dado un arreglo arr[] con N elementos, la tarea es encontrar el subarreglo más largo que tiene la forma de una montaña.
Un subarreglo de montaña consta de elementos que inicialmente están en orden ascendente hasta que se alcanza un elemento pico y, más allá del elemento pico, todos los demás elementos del subarreglo están en orden decreciente.
Ejemplos:
Entrada: arr = [2, 2, 2]
Salida: 0
Explicación:
No existe ningún subarreglo que muestre el comportamiento de un subarreglo de montaña.Entrada: arr = [1, 3, 1, 4, 5, 6, 7, 8, 9, 8, 7, 6, 5]
Salida: 11
Explicación:
Hay dos sub-arrays que pueden considerarse como sub-arrays de montaña arreglos El primero es del índice 0 – 2 (3 elementos) y el siguiente es del índice 2 – 12 (11 elementos). Como 11 > 2, nuestra respuesta es 11.
Enfoque ingenuo:
revise todos los subconjuntos posibles y compruebe si se trata de un subconjunto de montaña o no. Esto puede tomar mucho tiempo para encontrar la solución y la complejidad del tiempo para el enfoque anterior se puede estimar como O(N*N) para pasar por todos los subconjuntos posibles y O(N) para comprobar si se trata de un subconjunto de montaña. array o no. Por lo tanto, la complejidad de tiempo general para el programa es O(N 3 ) , que es muy alta.
Enfoque eficiente:
- Si la longitud de la array dada es menor que 3, imprima 0, ya que no es posible tener una sub-array de montaña en tal caso.
- Establezca la longitud máxima en 0 inicialmente.
- Utilice la técnica de dos punteros (puntero de ‘inicio’ y puntero de ‘final’) para encontrar el subarreglo de montaña más largo en el arreglo dado.
- Cuando se encuentre un subarreglo creciente, marque el índice inicial de ese subarreglo creciente en el puntero ‘comienzo’.
- Si se encuentra un valor de índice en el puntero ‘final’, restablezca los valores en ambos punteros, ya que marca el comienzo de una nueva subarray de montaña.
- Cuando se encuentre un subarreglo decreciente, marque el índice final del subarreglo de montaña en el puntero ‘final’.
- Calcule la longitud del subconjunto de montañas actual, compárelo con la longitud máxima actual de los subconjuntos de todas las montañas recorridos hasta ahora y siga actualizando la longitud máxima actual.
A continuación se muestra la implementación del enfoque eficiente descrito anteriormente:
C++
// C++ code for Longest Mountain Subarray
#include <bits/stdc++.h>
using namespace std;
// Function to find the
// longest mountain subarray
int LongestMountain(vector<int>& a)
{
int i = 0, j = -1,
k = -1, p = 0,
d = 0, n = 0;
// If the size of array is less
// than 3, the array won't show
// mountain like behaviour
if (a.size() < 3) {
return 0;
}
for (i = 0; i < a.size() - 1; i++) {
if (a[i + 1] > a[i]) {
// When a new mountain sub-array
// is found, there is a need to
// set the variables k, j to -1
// in order to help calculate the
// length of new mountain sub-array
if (k != -1) {
k = -1;
j = -1;
}
// j marks the starting index of a
// new mountain sub-array. So set the
// value of j to current index i.
if (j == -1) {
j = i;
}
}
else {
// Checks if next element is
// less than current element
if (a[i + 1] < a[i]) {
// Checks if starting element exists
// or not, if the starting element
// of the mountain sub-array exists
// then the index of ending element
// is stored in k
if (j != -1) {
k = i + 1;
}
// This condition checks if both
// starting index and ending index
// exists or not, if yes, the
// length is calculated.
if (k != -1 && j != -1) {
// d holds the length of the
// longest mountain sub-array.
// If the current length is
// greater than the
// calculated length, then
// value of d is updated.
if (d < k - j + 1) {
d = k - j + 1;
}
}
}
// ignore if there is no
// increase or decrease in
// the value of the next element
else {
k = -1;
j = -1;
}
}
}
// Checks and calculates
// the length if last element
// of the array is the last
// element of a mountain sub-array
if (k != -1 && j != -1) {
if (d < k - j + 1) {
d = k - j + 1;
}
}
return d;
}
// Driver code
int main()
{
vector<int> d = { 1, 3, 1, 4,
5, 6, 7, 8,
9, 8, 7, 6, 5 };
cout << LongestMountain(d)
<< endl;
return 0;
}
Java
// Java code for Longest Mountain Subarray
import java.io.*;
class GFG{
// Function to find the
// longest mountain subarray
public static int LongestMountain(int a[])
{
int i = 0, j = -1, k = -1, d = 0;
// If the size of array is less than 3,
// the array won't show mountain like
// behaviour
if (a.length < 3)
return 0;
for(i = 0; i < a.length - 1; i++)
{
if (a[i + 1] > a[i])
{
// When a new mountain sub-array is
// found, there is a need to set the
// variables k, j to -1 in order to
// help calculate the length of new
// mountain sub-array
if (k != -1)
{
k = -1;
j = -1;
}
// j marks the starting index of a
// new mountain sub-array. So set the
// value of j to current index i.
if (j == -1)
j = i;
}
else
{
// Checks if next element is
// less than current element
if (a[i + 1] < a[i])
{
// Checks if starting element exists
// or not, if the starting element of
// the mountain sub-array exists then
// the index of ending element is
// stored in k
if (j != -1)
k = i + 1;
// This condition checks if both
// starting index and ending index
// exists or not, if yes,the length
// is calculated.
if (k != -1 && j != -1)
{
// d holds the length of the
// longest mountain sub-array.
// If the current length is
// greater than the calculated
// length, then value of d is
// updated.
if (d < k - j + 1)
d = k - j + 1;
}
}
// Ignore if there is no increase
// or decrease in the value of the
// next element
else
{
k = -1;
j = -1;
}
}
}
// Checks and calculates the length
// if last element of the array is
// the last element of a mountain sub-array
if (k != -1 && j != -1)
{
if (d < k - j + 1)
d = k - j + 1;
}
return d;
}
// Driver code
public static void main (String[] args)
{
int a[] = { 1, 3, 1, 4, 5, 6, 7,
8, 9, 8, 7, 6, 5 };
System.out.println(LongestMountain(a));
}
}
// This code is contributed by piyush3010
Python3
# Python3 code for longest mountain subarray # Function to find the # longest mountain subarray def LongestMountain(a): i = 0 j = -1 k = -1 p = 0 d = 0 n = 0 # If the size of the array is less # than 3, the array won't show # mountain like behaviour if (len(a) < 3): return 0 for i in range(len(a) - 1): if (a[i + 1] > a[i]): # When a new mountain sub-array # is found, there is a need to # set the variables k, j to -1 # in order to help calculate the # length of new mountain sub-array if (k != -1): k = -1 j = -1 # j marks the starting index of a # new mountain sub-array. So set the # value of j to current index i. if (j == -1): j = i else: # Checks if next element is # less than current element if (a[i + 1] < a[i]): # Checks if starting element exists # or not, if the starting element # of the mountain sub-array exists # then the index of ending element # is stored in k if (j != -1): k = i + 1 # This condition checks if both # starting index and ending index # exists or not, if yes, the # length is calculated. if (k != -1 and j != -1): # d holds the length of the # longest mountain sub-array. # If the current length is # greater than the # calculated length, then # value of d is updated. if (d < k - j + 1): d = k - j + 1 # Ignore if there is no # increase or decrease in # the value of the next element else: k = -1 j = -1 # Checks and calculates # the length if last element # of the array is the last # element of a mountain sub-array if (k != -1 and j != -1): if (d < k - j + 1): d = k - j + 1 return d # Driver code d = [ 1, 3, 1, 4, 5, 6, 7, 8, 9, 8, 7, 6, 5 ] print(LongestMountain(d)) # This code is contributed by shubhamsingh10
C#
// C# code for the
// longest Mountain Subarray
using System;
class GFG{
// Function to find the
// longest mountain subarray
public static int longestMountain(int []a)
{
int i = 0, j = -1, k = -1,
p = 0, d = 0;
// If the size of array is less than 3,
// the array won't show mountain like
// behaviour
if (a.Length < 3)
return 0;
for(i = 0; i < a.Length - 1; i++)
{
if (a[i + 1] > a[i])
{
// When a new mountain sub-array is
// found, there is a need to set the
// variables k, j to -1 in order to
// help calculate the length of new
// mountain sub-array
if (k != -1)
{
k = -1;
j = -1;
}
// j marks the starting index of a
// new mountain sub-array. So set the
// value of j to current index i.
if (j == -1)
j = i;
}
else
{
// Checks if next element is
// less than current element
if (a[i + 1] < a[i])
{
// Checks if starting element exists
// or not, if the starting element of
// the mountain sub-array exists then
// the index of ending element is
// stored in k
if (j != -1)
k = i + 1;
// This condition checks if both
// starting index and ending index
// exists or not, if yes,the length
// is calculated.
if (k != -1 && j != -1)
{
// d holds the length of the
// longest mountain sub-array.
// If the current length is
// greater than the calculated
// length, then value of d is
// updated.
if (d < k - j + 1)
d = k - j + 1;
}
}
// Ignore if there is no increase
// or decrease in the value of the
// next element
else
{
k = -1;
j = -1;
}
}
}
// Checks and calculates the length
// if last element of the array is
// the last element of a mountain sub-array
if (k != -1 && j != -1)
{
if (d < k - j + 1)
d = k - j + 1;
}
return d;
}
// Driver code
public static void Main(String[] args)
{
int []a = {1, 3, 1, 4, 5, 6, 7,
8, 9, 8, 7, 6, 5};
Console.WriteLine(longestMountain(a));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript code for Longest Mountain Subarray
// Function to find the
// longest mountain subarray
function LongestMountain(a)
{
let i = 0, j = -1, k = -1,
p = 0, d = 0, n = 0;
// If the size of array is less than 3,
// the array won't show mountain like
// behaviour
if (a.length < 3)
return 0;
for(i = 0; i < a.length - 1; i++)
{
if (a[i + 1] > a[i])
{
// When a new mountain sub-array is
// found, there is a need to set the
// variables k, j to -1 in order to
// help calculate the length of new
// mountain sub-array
if (k != -1)
{
k = -1;
j = -1;
}
// j marks the starting index of a
// new mountain sub-array. So set the
// value of j to current index i.
if (j == -1)
j = i;
}
else
{
// Checks if next element is
// less than current element
if (a[i + 1] < a[i])
{
// Checks if starting element exists
// or not, if the starting element of
// the mountain sub-array exists then
// the index of ending element is
// stored in k
if (j != -1)
k = i + 1;
// This condition checks if both
// starting index and ending index
// exists or not, if yes,the length
// is calculated.
if (k != -1 && j != -1)
{
// d holds the length of the
// longest mountain sub-array.
// If the current length is
// greater than the calculated
// length, then value of d is
// updated.
if (d < k - j + 1)
d = k - j + 1;
}
}
// Ignore if there is no increase
// or decrease in the value of the
// next element
else
{
k = -1;
j = -1;
}
}
}
// Checks and calculates the length
// if last element of the array is
// the last element of a mountain sub-array
if (k != -1 && j != -1)
{
if (d < k - j + 1)
d = k - j + 1;
}
return d;
}
// Driver Code
let a = [ 1, 3, 1, 4, 5, 6, 7,
8, 9, 8, 7, 6, 5 ];
document.write(LongestMountain(a));
</script>
Producción:
11
Complejidad de Tiempo: O(N)
Complejidad de Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por vabzcode12 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA