Dada una array arr[] de tamaño N ( siempre potencia de 2 ), la tarea es encontrar la longitud de la array ordenada más larga a la que se puede reducir la array dada eliminando la mitad de la array en cada operación.
Ejemplos:
Entrada: arr[] = { 11, 12, 1, 2, 13, 14, 3, 4 }
Salida: 2
Explicación:
La eliminación de la primera mitad de arr[] modifica arr[] a {13, 14, 3, 4 }.
La eliminación de la primera mitad de arr[] modifica arr[] a {3, 4}.
Por lo tanto, la longitud de la array ordenada más larga posible es 2, que es la máxima posible.Entrada: arr[] = { 1, 2, 2, 4 }
Salida: 4
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos MaxLength , para almacenar la longitud máxima de la array ordenada que se puede obtener al realizar las operaciones dadas.
- Divida recursivamente la array en dos mitades iguales y para cada mitad, verifique si la partición de la array está ordenada o no . Si se determina que es cierto, actualice MaxLength a la longitud de la partición.
- Finalmente, imprima el valor de MaxLength .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if the subarray
// arr[i..j] is a sorted subarray or not
int isSortedparitions(int arr[],
int i, int j)
{
// Traverse all elements of
// the subarray arr[i...j]
for (int k = i + 1; k <= j; k++) {
// If the previous element of the
// subarray exceeds current element
if (arr[k] < arr[k - 1]) {
// Return 0
return 0;
}
}
// Return 1
return 1;
}
// Recursively partition the array
// into two equal halves
int partitionsArr(int arr[],
int i, int j)
{
// If atmost one element is left
// in the subarray arr[i..j]
if (i >= j)
return 1;
// Checks if subarray arr[i..j] is
// a sorted subarray or not
bool flag = isSortedparitions(
arr, i, j);
// If the subarray arr[i...j]
// is a sorted subarray
if (flag) {
return (j - i + 1);
}
// Stores middle element
// of the subarray arr[i..j]
int mid = (i + j) / 2;
// Recursively partition the current
// subarray arr[i..j] into equal halves
int X = partitionsArr(arr, i, mid);
int Y = partitionsArr(arr, mid + 1, j);
return max(X, Y);
}
// Driver Code
int main()
{
int arr[] = { 11, 12, 1, 2,
13, 14, 3, 4 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << partitionsArr(
arr, 0, N - 1);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to check if the subarray
// arr[i..j] is a sorted subarray or not
static int isSortedparitions(int arr[],
int i, int j)
{
// Traverse all elements of
// the subarray arr[i...j]
for(int k = i + 1; k <= j; k++)
{
// If the previous element of the
// subarray exceeds current element
if (arr[k] < arr[k - 1])
{
// Return 0
return 0;
}
}
// Return 1
return 1;
}
// Recursively partition the array
// into two equal halves
static int partitionsArr(int arr[], int i,
int j)
{
// If atmost one element is left
// in the subarray arr[i..j]
if (i >= j)
return 1;
// Checks if subarray arr[i..j] is
// a sorted subarray or not
int flag = (int)isSortedparitions(arr, i, j);
// If the subarray arr[i...j]
// is a sorted subarray
if (flag != 0)
{
return (j - i + 1);
}
// Stores middle element
// of the subarray arr[i..j]
int mid = (i + j) / 2;
// Recursively partition the current
// subarray arr[i..j] into equal halves
int X = partitionsArr(arr, i, mid);
int Y = partitionsArr(arr, mid + 1, j);
return Math.max(X, Y);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 11, 12, 1, 2,
13, 14, 3, 4 };
int N = arr.length;
System.out.print(partitionsArr(
arr, 0, N - 1));
}
}
// This code is contributed by susmitakundugoaldanga
Python3
# Python3 program to implement # the above approach # Function to check if the subarray # arr[i..j] is a sorted subarray or not def isSortedparitions(arr, i, j): # Traverse all elements of # the subarray arr[i...j] for k in range(i + 1, j + 1): # If the previous element of the # subarray exceeds current element if (arr[k] < arr[k - 1]): # Return 0 return 0 # Return 1 return 1 # Recursively partition the array # into two equal halves def partitionsArr(arr, i, j): # If atmost one element is left # in the subarray arr[i..j] if (i >= j): return 1 # Checks if subarray arr[i..j] is # a sorted subarray or not flag = int(isSortedparitions(arr, i, j)) # If the subarray arr[i...j] # is a sorted subarray if (flag != 0): return (j - i + 1) # Stores middle element # of the subarray arr[i..j] mid = (i + j) // 2 # Recursively partition the current # subarray arr[i..j] into equal halves X = partitionsArr(arr, i, mid); Y = partitionsArr(arr, mid + 1, j) return max(X, Y) # Driver Code if __name__ == '__main__': arr = [ 11, 12, 1, 2, 13, 14, 3, 4 ] N = len(arr) print(partitionsArr(arr, 0, N - 1)) # This code is contributed by Princi Singh
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to check if the subarray
// arr[i..j] is a sorted subarray or not
static int isSortedparitions(int[] arr,
int i, int j)
{
// Traverse all elements of
// the subarray arr[i...j]
for(int k = i + 1; k <= j; k++)
{
// If the previous element of the
// subarray exceeds current element
if (arr[k] < arr[k - 1])
{
// Return 0
return 0;
}
}
// Return 1
return 1;
}
// Recursively partition the array
// into two equal halves
static int partitionsArr(int[] arr, int i,
int j)
{
// If atmost one element is left
// in the subarray arr[i..j]
if (i >= j)
return 1;
// Checks if subarray arr[i..j] is
// a sorted subarray or not
int flag = (int)isSortedparitions(arr, i, j);
// If the subarray arr[i...j]
// is a sorted subarray
if (flag != 0)
{
return (j - i + 1);
}
// Stores middle element
// of the subarray arr[i..j]
int mid = (i + j) / 2;
// Recursively partition the current
// subarray arr[i..j] into equal halves
int X = partitionsArr(arr, i, mid);
int Y = partitionsArr(arr, mid + 1, j);
return Math.Max(X, Y);
}
// Driver Code
public static void Main()
{
int[] arr = { 11, 12, 1, 2,
13, 14, 3, 4 };
int N = arr.Length;
Console.Write(partitionsArr(
arr, 0, N - 1));
}
}
// This code is contributed by code_hunt
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to check if the subarray
// arr[i..j] is a sorted subarray or not
function isSortedparitions(arr, i, j)
{
// Traverse all elements of
// the subarray arr[i...j]
for (var k = i + 1; k <= j; k++) {
// If the previous element of the
// subarray exceeds current element
if (arr[k] < arr[k - 1]) {
// Return 0
return 0;
}
}
// Return 1
return 1;
}
// Recursively partition the array
// into two equal halves
function partitionsArr(arr, i, j)
{
// If atmost one element is left
// in the subarray arr[i..j]
if (i >= j)
return 1;
// Checks if subarray arr[i..j] is
// a sorted subarray or not
var flag = isSortedparitions(
arr, i, j);
// If the subarray arr[i...j]
// is a sorted subarray
if (flag) {
return (j - i + 1);
}
// Stores middle element
// of the subarray arr[i..j]
var mid = parseInt((i + j) / 2);
// Recursively partition the current
// subarray arr[i..j] into equal halves
var X = partitionsArr(arr, i, mid);
var Y = partitionsArr(arr, mid + 1, j);
return Math.max(X, Y);
}
// Driver Code
var arr = [11, 12, 1, 2,
13, 14, 3, 4 ];
var N = arr.length;
document.write( partitionsArr(
arr, 0, N - 1));
</script>
Producción:
2
Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ManikantaBandla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA