Dada una array arr[] de N enteros, la tarea es encontrar si la array se puede dividir en 2 subarreglos, de modo que la primera subarreglo sea estrictamente creciente y la segunda sea estrictamente decreciente o viceversa. Si la array dada se puede dividir, imprima «Sí» , de lo contrario, imprima «No» .
Ejemplos:
Entrada: arr[] = {3, 1, -2, -2, -1, 3}
Salida: Sí
Explicación:
El primer subconjunto {3, 1, -2} que es estrictamente decreciente y el segundo subconjunto es { -2, 1, 3} es estrictamente creciente.Entrada: arr[] = {1, 1, 2, 3, 4, 5}
Salida: No
Explicación:
La array completa está aumentando.
Enfoque ingenuo: la idea ingenua es dividir la array en dos subarreglos en todos los índices posibles y verificar explícitamente si el primer subarreglo es estrictamente creciente y el segundo subarreglo estrictamente decreciente o viceversa. Si podemos dividir cualquier subarreglo, imprima «Sí» , de lo contrario, imprima «No» .
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, recorra la array y verifique la secuencia estrictamente creciente y luego verifique la subsecuencia estrictamente decreciente o viceversa. A continuación se muestran los pasos:
- Si arr[1] > arr[0], compruebe si aumenta estrictamente y luego disminuye estrictamente como:
- Compruebe cada par consecutivo hasta que en cualquier índice i arr[i + 1] sea menor que arr[i].
- Ahora, desde el índice i + 1, verifique para cada par consecutivo, verifique si arr [i + 1] es menor que arr [i] hasta el final de la array o no. Si en cualquier índice i, arr[i] es menor que arr[i + 1] , rompa el ciclo.
- Si llegamos al final en el paso anterior, imprima «Sí» . De lo contrario, imprima «No» .
- Si arr[1] < arr[0], compruebe si es estrictamente decreciente y luego estrictamente creciente como:
- Compruebe cada par consecutivo hasta que en cualquier índice i arr[i + 1] sea mayor que arr[i].
- Ahora, desde el índice i + 1, verifique para cada par consecutivo, verifique si arr [i + 1] es mayor que arr [i] hasta el final de la array o no. Si en cualquier índice i, arr[i] es mayor que arr[i + 1] , rompa el ciclo.
- Si llegamos al final en el paso anterior, imprima «Sí» . De lo contrario, imprima «No» .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if the given array
// forms an increasing decreasing
// sequence or vice versa
bool canMake(int n, int ar[])
{
// Base Case
if (n == 1)
return true;
else {
// First subarray is
// strictly increasing
if (ar[0] < ar[1]) {
int i = 1;
// Check for strictly
// increasing condition
// & find the break point
while (i < n
&& ar[i - 1] < ar[i]) {
i++;
}
// Check for strictly
// decreasing condition
// & find the break point
while (i + 1 < n
&& ar[i] > ar[i + 1]) {
i++;
}
// If i is equal to
// length of array
if (i >= n - 1)
return true;
else
return false;
}
// First subarray is
// strictly Decreasing
else if (ar[0] > ar[1]) {
int i = 1;
// Check for strictly
// increasing condition
// & find the break point
while (i < n
&& ar[i - 1] > ar[i]) {
i++;
}
// Check for strictly
// increasing condition
// & find the break point
while (i + 1 < n
&& ar[i] < ar[i + 1]) {
i++;
}
// If i is equal to
// length of array - 1
if (i >= n - 1)
return true;
else
return false;
}
// Condition if ar[0] == ar[1]
else {
for (int i = 2; i < n; i++) {
if (ar[i - 1] <= ar[i])
return false;
}
return true;
}
}
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 1, 2, 3, 4, 5 };
int n = sizeof arr / sizeof arr[0];
// Function Call
if (canMake(n, arr)) {
cout << "Yes";
}
else {
cout << "No";
}
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to check if the given array
// forms an increasing decreasing
// sequence or vice versa
static boolean canMake(int n, int ar[])
{
// Base Case
if (n == 1)
return true;
else
{
// First subarray is
// strictly increasing
if (ar[0] < ar[1])
{
int i = 1;
// Check for strictly
// increasing condition
// & find the break point
while (i < n && ar[i - 1] < ar[i])
{
i++;
}
// Check for strictly
// decreasing condition
// & find the break point
while (i + 1 < n && ar[i] > ar[i + 1])
{
i++;
}
// If i is equal to
// length of array
if (i >= n - 1)
return true;
else
return false;
}
// First subarray is
// strictly Decreasing
else if (ar[0] > ar[1])
{
int i = 1;
// Check for strictly
// increasing condition
// & find the break point
while (i < n && ar[i - 1] > ar[i])
{
i++;
}
// Check for strictly
// increasing condition
// & find the break point
while (i + 1 < n && ar[i] < ar[i + 1])
{
i++;
}
// If i is equal to
// length of array - 1
if (i >= n - 1)
return true;
else
return false;
}
// Condition if ar[0] == ar[1]
else
{
for (int i = 2; i < n; i++)
{
if (ar[i - 1] <= ar[i])
return false;
}
return true;
}
}
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = { 1, 2, 3, 4, 5 };
int n = arr.length;
// Function Call
if (!canMake(n, arr)) {
System.out.print("Yes");
}
else
{
System.out.print("No");
}
}
}
// This code is contributed by Rohit_ranjan
Python3
# Python3 program for the above approach
# Function to check if the given array
# forms an increasing decreasing
# sequence or vice versa
def canMake(n, ar):
# Base Case
if (n == 1):
return True;
else:
# First subarray is
# strictly increasing
if (ar[0] < ar[1]):
i = 1;
# Check for strictly
# increasing condition
# & find the break point
while (i < n and ar[i - 1] < ar[i]):
i += 1;
# Check for strictly
# decreasing condition
# & find the break point
while (i + 1 < n and ar[i] > ar[i + 1]):
i += 1;
# If i is equal to
# length of array
if (i >= n - 1):
return True;
else:
return False;
# First subarray is
# strictly Decreasing
elif (ar[0] > ar[1]):
i = 1;
# Check for strictly
# increasing condition
# & find the break point
while (i < n and ar[i - 1] > ar[i]):
i += 1;
# Check for strictly
# increasing condition
# & find the break point
while (i + 1 < n and ar[i] < ar[i + 1]):
i += 1;
# If i is equal to
# length of array - 1
if (i >= n - 1):
return True;
else:
return False;
# Condition if ar[0] == ar[1]
else:
for i in range(2, n):
if (ar[i - 1] <= ar[i]):
return False;
return True;
# Driver Code
# Given array arr
arr = [1, 2, 3, 4, 5];
n = len(arr);
# Function Call
if (canMake(n, arr)==False):
print("Yes");
else:
print("No");
# This code is contributed by PrinciRaj1992
C#
// C# program for the above approach
using System;
class GFG{
// Function to check if the given array
// forms an increasing decreasing
// sequence or vice versa
static bool canMake(int n, int []ar)
{
// Base Case
if (n == 1)
return true;
else
{
// First subarray is
// strictly increasing
if (ar[0] < ar[1])
{
int i = 1;
// Check for strictly
// increasing condition
// & find the break point
while (i < n && ar[i - 1] < ar[i])
{
i++;
}
// Check for strictly
// decreasing condition
// & find the break point
while (i + 1 < n && ar[i] > ar[i + 1])
{
i++;
}
// If i is equal to
// length of array
if (i >= n - 1)
return true;
else
return false;
}
// First subarray is
// strictly Decreasing
else if (ar[0] > ar[1])
{
int i = 1;
// Check for strictly
// increasing condition
// & find the break point
while (i < n && ar[i - 1] > ar[i])
{
i++;
}
// Check for strictly
// increasing condition
// & find the break point
while (i + 1 < n && ar[i] < ar[i + 1])
{
i++;
}
// If i is equal to
// length of array - 1
if (i >= n - 1)
return true;
else
return false;
}
// Condition if ar[0] == ar[1]
else
{
for (int i = 2; i < n; i++)
{
if (ar[i - 1] <= ar[i])
return false;
}
return true;
}
}
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int []arr = { 1, 2, 3, 4, 5 };
int n = arr.Length;
// Function Call
if (!canMake(n, arr))
{
Console.Write("Yes");
}
else
{
Console.Write("No");
}
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program for the above approach
// Function to check if the given array
// forms an increasing decreasing
// sequence or vice versa
function canMake(n, ar)
{
// Base Case
if (n == 1)
return true;
else
{
// First subarray is
// strictly increasing
if (ar[0] < ar[1])
{
let i = 1;
// Check for strictly
// increasing condition
// & find the break point
while (i < n && ar[i - 1] < ar[i])
{
i++;
}
// Check for strictly
// decreasing condition
// & find the break point
while (i + 1 < n && ar[i] > ar[i + 1])
{
i++;
}
// If i is equal to
// length of array
if (i >= n - 1)
return true;
else
return false;
}
// First subarray is
// strictly Decreasing
else if (ar[0] > ar[1])
{
let i = 1;
// Check for strictly
// increasing condition
// & find the break point
while (i < n && ar[i - 1] > ar[i])
{
i++;
}
// Check for strictly
// increasing condition
// & find the break point
while (i + 1 < n && ar[i] < ar[i + 1])
{
i++;
}
// If i is equal to
// length of array - 1
if (i >= n - 1)
return true;
else
return false;
}
// Condition if ar[0] == ar[1]
else
{
for(let i = 2; i < n; i++)
{
if (ar[i - 1] <= ar[i])
return false;
}
return true;
}
}
}
// Driver Code
// Given array arr[]
let arr = [ 1, 2, 3, 4, 5 ];
let n = arr.length;
// Function Call
if (!canMake(n, arr))
{
document.write("Yes");
}
else
{
document.write("No");
}
// This code is contributed by sravan kumar
</script>
Producción:
No
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por angelina20 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA