Dada una array arr[] de N elementos distintos y un rango de índice [L, R] . La tarea es encontrar si una cresta está presente en ese rango de índice en la array o no. Cualquier elemento arr[i] en el subarreglo arr[L…R] se llama cresta si todos los elementos del subarreglo arr[L…i] son estrictamente crecientes y todos los elementos del subarreglo arr[i…R] son estrictamente decrecientes .
Ejemplos:
Entrada: arr[] = {2, 1, 3, 5, 12, 11, 7, 9}, L = 2, R = 6
Salida: Sí El
elemento 12 es una cresta en el subarreglo {3, 5, 12, 11 , 7}.
Entrada: arr[] = {2, 1, 3, 5, 12, 11, 7, 9}, L = 0, R = 2
Salida: No
Acercarse:
- Compruebe si en el rango de índice dado [L, R] existe un elemento que satisface la Propiedad donde arr[i – 1] ≥ arr[i] ≤ arr[i + 1] .
- Si algún elemento en el rango dado satisface la propiedad anterior, entonces el rango dado no puede contener una cresta; de lo contrario, la cresta siempre es posible.
- Para encontrar qué elemento satisface la propiedad anterior, mantenga una array presente[] donde presente[i] será 1 si arr[i – 1] ≥ arr[i] ≤ arr[i + 1] de lo contrario presente[i] será 0 .
- Ahora convierta la array present[] a su suma acumulativa donde present[i] ahora representará el número de elementos en el rango de índice [0, i] que satisfacen la propiedad.
- Para que un rango de índice [L, R] contenga una cresta, present[L] debe ser igual a present[R – 1] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function that returns true if the
// array contains a crest in
// the index range [L, R]
bool hasCrest(int arr[], int n, int L, int R)
{
// To keep track of elements
// which satisfy the Property
int present[n] = { 0 };
for (int i = 1; i <= n - 2; i++) {
// Property is satisfied for
// the current element
if ((arr[i] <= arr[i + 1])
&& (arr[i] <= arr[i - 1])) {
present[i] = 1;
}
}
// Cumulative Sum
for (int i = 1; i < n; i++) {
present[i] += present[i - 1];
}
// If a crest is present in
// the given index range
if (present[L] == present[R - 1])
return true;
return false;
}
// Driver code
int main()
{
int arr[] = { 2, 1, 3, 5, 12, 11, 7, 9 };
int N = sizeof(arr) / sizeof(arr[0]);
int L = 2;
int R = 6;
if (hasCrest(arr, N, L, R))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function that returns true if the
// array contains a crest in
// the index range [L, R]
static boolean hasCrest(int arr[], int n,
int L, int R)
{
// To keep track of elements
// which satisfy the Property
int []present = new int[n];
for(int i = 0; i < n; i++)
{
present[i] = 0;
}
for (int i = 1; i <= n - 2; i++)
{
// Property is satisfied for
// the current element
if ((arr[i] <= arr[i + 1]) &&
(arr[i] <= arr[i - 1]))
{
present[i] = 1;
}
}
// Cumulative Sum
for (int i = 1; i < n; i++)
{
present[i] += present[i - 1];
}
// If a crest is present in
// the given index range
if (present[L] == present[R - 1])
return true;
return false;
}
// Driver code
public static void main(String args[])
{
int arr[] = { 2, 1, 3, 5, 12, 11, 7, 9 };
int N = arr.length;
int L = 2;
int R = 6;
if (hasCrest(arr, N, L, R))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by Surendra_Gangwar
Python3
# Python3 implementation of the approach
# Function that returns true if the
# array contains a crest in
# the index range [L, R]
def hasCrest(arr, n, L, R) :
# To keep track of elements
# which satisfy the Property
present = [0] * n ;
for i in range(1, n - 2 + 1) :
# Property is satisfied for
# the current element
if ((arr[i] <= arr[i + 1]) and
(arr[i] <= arr[i - 1])) :
present[i] = 1;
# Cumulative Sum
for i in range(1, n) :
present[i] += present[i - 1];
# If a crest is present in
# the given index range
if (present[L] == present[R - 1]) :
return True;
return False;
# Driver code
if __name__ == "__main__" :
arr = [ 2, 1, 3, 5, 12, 11, 7, 9 ];
N = len(arr);
L = 2;
R = 6;
if (hasCrest(arr, N, L, R)) :
print("Yes");
else :
print("No");
# This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
// Function that returns true if the
// array contains a crest in
// the index range [L, R]
static bool hasCrest(int []arr, int n,
int L, int R)
{
// To keep track of elements
// which satisfy the Property
int []present = new int[n];
for(int i = 0; i < n; i++)
{
present[i] = 0;
}
for (int i = 1; i <= n - 2; i++)
{
// Property is satisfied for
// the current element
if ((arr[i] <= arr[i + 1]) &&
(arr[i] <= arr[i - 1]))
{
present[i] = 1;
}
}
// Cumulative Sum
for (int i = 1; i < n; i++)
{
present[i] += present[i - 1];
}
// If a crest is present in
// the given index range
if (present[L] == present[R - 1])
return true;
return false;
}
// Driver code
public static void Main(String []args)
{
int []arr = { 2, 1, 3, 5, 12, 11, 7, 9 };
int N = arr.Length;
int L = 2;
int R = 6;
if (hasCrest(arr, N, L, R))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript implementation of the approach
// Function that returns true if the
// array contains a crest in
// the index range [L, R]
function hasCrest(arr, n, L, R)
{
// To keep track of elements
// which satisfy the Property
let present = new Uint8Array(n);
for (let i = 1; i <= n - 2; i++) {
// Property is satisfied for
// the current element
if ((arr[i] <= arr[i + 1])
&& (arr[i] <= arr[i - 1])) {
present[i] = 1;
}
}
// Cumulative Sum
for (let i = 1; i < n; i++) {
present[i] += present[i - 1];
}
// If a crest is present in
// the given index range
if (present[L] == present[R - 1])
return true;
return false;
}
// Driver code
let arr = [ 2, 1, 3, 5, 12, 11, 7, 9 ];
let N = arr.length;
let L = 2;
let R = 6;
if (hasCrest(arr, N, L, R))
document.write("Yes");
else
document.write("No");
// This code is contributed by Surbhi Tyagi.
</script>
Producción:
Yes
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(n)