Dado un arreglo arr[0..n-1] de n enteros, encuentre el subarreglo de longitud máxima tal que su primer elemento sea mayor o igual que el último elemento del subarreglo.
Ejemplos:
Input : arr[] = {-5, -1, 7, 5, 1, -2}
Output : 5
Explanation : Subarray {-1, 7, 5, 1, -2} forms maximum
length subarray with its first element greater than last.
Input : arr[] = {1, 5, 7}
Output : 1
El enfoque ingenuo es usar dos bucles anidados para cada posible elemento inicial y final del subarreglo y, si cumple la condición, actualice la respuesta en consecuencia.
Complejidad del tiempo – O(n^2)
Un mejor enfoque es utilizar la búsqueda binaria . En este enfoque, para cada elemento del arreglo, maximizamos la longitud del subarreglo que termina en ese elemento. Luego tomamos el máximo de todas las longitudes.
Tomaremos otra array que se utiliza como nuestro espacio de búsqueda para elegir el elemento inicial de. Seguiremos agregando elementos a medida que atravesamos la array si el elemento es mayor que todos los elementos anteriores presentes en el espacio de búsqueda.
La observación clave aquí es que agregaremos un elemento a nuestro espacio de búsqueda solo cuando sea mayor que todos los elementos del espacio de búsqueda porque si el elemento es más bajo que cualquier otro elemento, nunca se puede elegir como el primer elemento del máximo. subarreglo de longitud ya que tendríamos una mejor opción.
Dado que el espacio de búsqueda siempre se ordena en orden creciente, solo necesitamos comparar el elemento actual de la array con el último elemento del espacio de búsqueda y, si y solo si es mayor que el último elemento, lo agregamos al espacio de búsqueda; de lo contrario, no.
A continuación se muestra la implementación del enfoque anterior.
C++
// CPP program to find length of the longest
// array with first element smaller than or
// equal to last element.
#include <algorithm>
#include <iostream>
using namespace std;
// Search function for searching the first element of the
// subarray which is greater or equal to the last element(num)
int binarySearch(int* searchSpace, int s, int e, int num)
{
int ans;
while (s <= e) {
int mid = (s + e) / 2;
if (searchSpace[mid] >= num) {
ans = mid;
e = mid - 1;
}
else
s = mid + 1;
}
return ans;
}
// Returns length of the longest array with first
// element smaller than the last element.
int longestSubArr(int* arr, int n)
{
// Search space for the potential first elements.
int searchSpace[n];
// It will store the Indexes of the elements
// of search space in the original array.
int index[n];
// Initially the search space is empty.
int j = 0;
int ans = 0;
for (int i = 0; i < n; ++i) {
// We will add an ith element in the search
// space if the search space is empty or if
// the ith element is greater than the last
// element of the search space.
if (j == 0 or searchSpace[j - 1] < arr[i]) {
searchSpace[j] = arr[i];
index[j] = i;
j++;
}
// we will search for the index first element in the
// search space and we will use it find the
// index of it in the original array.
int idx = binarySearch(searchSpace, 0, j - 1, arr[i]);
// Update the answer if the length of the subarray is
// greater than the previously calculated lengths.
ans = max(ans, i - index[idx] + 1);
}
return ans;
}
int main(int argc, char const* argv[])
{
int arr[] = { -5, -1, 7, 5, 1, -2 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << longestSubArr(arr, n) << endl;
return 0;
}
Java
// Java program to find length
// of the longest array with
// first element smaller than
// or equal to last element.
class GFG
{
// Search function for searching
// the first element of the
// subarray which is greater or
// equal to the last element(num)
static int binarySearch(int []searchSpace, int s,
int e, int num)
{
int ans = 0;
while (s <= e)
{
int mid = (s + e) / 2;
if (searchSpace[mid] >= num)
{
ans = mid;
e = mid - 1;
}
else
s = mid + 1;
}
return ans;
}
// Returns length of the longest
// array with first element smaller
// than the last element.
static int longestSubArr(int []arr, int n)
{
// Search space for the
// potential first elements.
int []searchSpace = new int[n];
// It will store the Indexes
// of the elements of search
// space in the original array.
int []index = new int[n];
// Initially the search
// space is empty.
int j = 0;
int ans = 0;
for (int i = 0; i < n; ++i)
{
// We will add an ith element
// in the search space if the
// search space is empty or if
// the ith element is greater
// than the last element of
// the search space.
if (j == 0 || searchSpace[j - 1] < arr[i])
{
searchSpace[j] = arr[i];
index[j] = i;
j++;
}
// we will search for the index
// first element in the search
// space and we will use it find
// the index of it in the original array.
int idx = binarySearch(searchSpace, 0,
j - 1, arr[i]);
// Update the answer if the
// length of the subarray is
// greater than the previously
// calculated lengths.
ans = Math.max(ans, i - index[idx] + 1);
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { -5, -1, 7, 5, 1, -2 };
int n = arr.length;
System.out.println(longestSubArr(arr, n));
}
}
// This code is contributed
// by ChitraNayal
Python3
# Python 3 program to find # length of the longest array # with first element smaller # than or equal to last element. # Search function for searching # the first element of the # subarray which is greater or # equal to the last element(num) def binarySearch(searchSpace, s, e, num): while (s <= e): mid = (s + e) // 2 if searchSpace[mid] >= num : ans = mid e = mid - 1 else: s = mid + 1 return ans # Returns length of the longest # array with first element # smaller than the last element. def longestSubArr(arr, n): # Search space for the # potential first elements. searchSpace = [None] * n # It will store the Indexes # of the elements of search # space in the original array. index = [None] * n # Initially the search # space is empty. j = 0 ans = 0 for i in range(n): # We will add an ith element # in the search space if the # search space is empty or if # the ith element is greater # than the last element of # the search space. if (j == 0 or searchSpace[j - 1] < arr[i]) : searchSpace[j] = arr[i] index[j] = i j += 1 # we will search for the index # first element in the search # space and we will use it # find the index of it in the # original array. idx = binarySearch(searchSpace, 0, j - 1, arr[i]) # Update the answer if the length # of the subarray is greater than # the previously calculated lengths. ans = max(ans, i - index[idx] + 1) return ans if __name__ == "__main__": arr = [ -5, -1, 7, 5, 1, -2 ] n = len(arr) print(longestSubArr(arr, n)) # This code is contributed # by ChitraNayal
C#
// C# program to find length
// of the longest array with
// first element smaller than
// or equal to last element.
using System;
class GFG
{
// Search function for searching
// the first element of the
// subarray which is greater or
// equal to the last element(num)
static int binarySearch(int[] searchSpace,
int s, int e, int num)
{
int ans = 0;
while (s <= e)
{
int mid = (s + e) / 2;
if (searchSpace[mid] >= num)
{
ans = mid;
e = mid - 1;
}
else
s = mid + 1;
}
return ans;
}
// Returns length of the longest
// array with first element smaller
// than the last element.
static int longestSubArr(int[] arr, int n)
{
// Search space for the
// potential first elements.
int[] searchSpace = new int[n];
// It will store the Indexes
// of the elements of search
// space in the original array.
int[] index = new int[n];
// Initially the search
// space is empty.
int j = 0;
int ans = 0;
for (int i = 0; i < n; ++i)
{
// We will add an ith element
// in the search space if the
// search space is empty or if
// the ith element is greater
// than the last element of
// the search space.
if (j == 0 || searchSpace[j - 1] < arr[i])
{
searchSpace[j] = arr[i];
index[j] = i;
j++;
}
// we will search for the index
// first element in the search
// space and we will use it find the
// index of it in the original array.
int idx = binarySearch(searchSpace, 0,
j - 1, arr[i]);
// Update the answer if the
// length of the subarray is
// greater than the previously
// calculated lengths.
ans = Math.Max(ans, i - index[idx] + 1);
}
return ans;
}
// Driver code
public static void Main()
{
int[] arr = { -5, -1, 7, 5, 1, -2 };
int n = arr.Length;
Console.Write(longestSubArr(arr, n));
}
}
// This code is contributed
// by ChitraNayal
PHP
<?php
// PHP program to find length
// of the longest array with
// first element smaller than
// or equal to last element.
// Search function for searching
// the first element of the
// subarray which is greater or
// equal to the last element(num)
function binarySearch($searchSpace,
$s, $e, $num)
{
$ans = 0;
while ($s <= $e)
{
$mid = ($s + $e) / 2;
if ($searchSpace[$mid] >= $num)
{
$ans = $mid;
$e = $mid - 1;
}
else
{
$s = $mid + 1;
}
}
return $ans;
}
// Returns length of the longest
// array with first element smaller
// than the last element.
function longestSubArr(&$arr, $n)
{
// Search space for the
// potential first elements.
// It will store the Indexes
// of the elements of search
// space in the original array.
// Initially the search
// space is empty.
$j = 0;
$ans = 0;
for ($i = 0; $i < $n; ++$i)
{
// We will add an ith element
// in the search space if the
// search space is empty or if
// the ith element is greater
// than the last element of the
// search space.
if ($j == 0 or
$searchSpace[$j - 1] < $arr[$i])
{
$searchSpace[$j] = $arr[$i];
$index[$j] = $i;
$j++;
}
// we will search for the index
// first element in the search
// space and we will use it find
// the index of it in the original
// array.
$idx = binarySearch($searchSpace, 0,
$j - 1, $arr[$i]);
// Update the answer if the length
// of the subarray is greater than
// the previously calculated lengths.
$ans = max($ans, $i - $index[$idx] + 1);
}
return $ans;
}
// Driver code
$arr = array(-5, -1, 7, 5, 1, -2);
$n = sizeof($arr);
echo (longestSubArr($arr, $n)) ;
// This code is contributed
// by Shivi_Aggarwal
?>
Javascript
<script>
// Javascript program to find length
// of the longest array with
// first element smaller than
// or equal to last element.
// Search function for searching
// the first element of the
// subarray which is greater or
// equal to the last element(num)
function binarySearch(searchSpace, s, e, num)
{
let ans = 0;
while (s <= e)
{
let mid = Math.floor((s + e) / 2);
if (searchSpace[mid] >= num)
{
ans = mid;
e = mid - 1;
}
else
s = mid + 1;
}
return ans;
}
// Returns length of the longest
// array with first element smaller
// than the last element.
function longestSubArr(arr, n)
{
// Search space for the
// potential first elements.
let searchSpace = new Array(n);
// It will store the Indexes
// of the elements of search
// space in the original array.
let index = new Array(n);
// Initially the search
// space is empty.
let j = 0;
let ans = 0;
for(let i = 0; i < n; ++i)
{
// We will add an ith element
// in the search space if the
// search space is empty or if
// the ith element is greater
// than the last element of
// the search space.
if (j == 0 || searchSpace[j - 1] < arr[i])
{
searchSpace[j] = arr[i];
index[j] = i;
j++;
}
// We will search for the index
// first element in the search
// space and we will use it find
// the index of it in the original array.
let idx = binarySearch(searchSpace, 0,
j - 1, arr[i]);
// Update the answer if the
// length of the subarray is
// greater than the previously
// calculated lengths.
ans = Math.max(ans, i - index[idx] + 1);
}
return ans;
}
// Driver code
let arr = [ -5, -1, 7, 5, 1, -2 ];
let n = arr.length;
document.write(longestSubArr(arr, n));
// This code is contributed by avanitrachhadiya2155
</script>
Producción
5
Complejidad del tiempo: (N * log N) La
función de búsqueda binaria toma el tiempo Log N y se llamará N veces.
Publicación traducida automáticamente
Artículo escrito por imdhruvgupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA