Dada una array arr[] de tamaño N , la tarea es encontrar el número de arrays de prefijos cuyo máximo sea menor que el elemento máximo en la array de sufijos restante.
Ejemplos:
Entrada: arr[] = {2, 3, 4, 8, 1, 4}
Salida: 3
Explicación:
array de prefijos = {2}, {2, 3}, {2, 3, 4}, {2, 3, 4, 8}, {2, 3, 4, 8, 1}
Sufijo respectivo = {3, 4, 8, 1, 4}, {4, 8, 1, 4}, {8, 1, 4}, { 1, 4}, {4}
Solo las 3 primeras arrays de prefijos tienen un elemento de valor máximo inferior al elemento de valor máximo en la array de sufijos respectiva.Entrada: arr[] = {4, 4, 4, 4, 5}
Salida: 4
Enfoque ingenuo: el enfoque más simple es encontrar todos los prefijos y sufijos posibles de la array dada y contar la cantidad de índices donde el elemento máximo en la array de prefijos es menor que el elemento máximo en la array de sufijos.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es almacenar el valor máximo para cada prefijo y sufijo de la array y luego calcular la cantidad de arrays de prefijos con un valor máximo menor que su correspondiente array de sufijos. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos ans y dos arrays prefix[] y suffix[] de tamaño N .
- Recorra la array arr[] sobre el rango [0, N – 1] y para cada i -ésimo índice en prefix[] , almacene el elemento máximo como prefix[i] = max(prefix[i – 1], arr[i] ) .
- Recorra la array dada en el orden inverso sobre el rango [N – 1, 0] y para cada i -ésimo índice en sufijo[] , almacene el elemento máximo como sufijo[i] = max(sufijo[i + 1], arr[ yo]) .
- Ahora, recorra la array arr[] sobre el rango [0, N – 2] y si prefix[i] es menor que suffix[i] , entonces incremente ans en 1 .
- Después de completar los pasos anteriores, imprima el valor de ans como resultado.
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 print the count of indices
// in which the maximum in prefix arrays
// is less than that in the suffix array
void count(int a[], int n)
{
// If size of array is 1
if (n == 1) {
cout << 0;
return;
}
// pre[]: Prefix array
// suf[]: Suffix array
int pre[n - 1], suf[n - 1];
int max = a[0];
// Stores the required count
int ans = 0, i;
pre[0] = a[0];
// Find the maximum in prefix array
for (i = 1; i < n - 1; i++) {
if (a[i] > max)
max = a[i];
pre[i] = max;
}
max = a[n - 1];
suf[n - 2] = a[n - 1];
// Find the maximum in suffix array
for (i = n - 2; i >= 1; i--) {
if (a[i] > max)
max = a[i];
suf[i - 1] = max;
}
// Traverse the array
for (i = 0; i < n - 1; i++) {
// If maximum in prefix array
// is less than maximum in
// the suffix array
if (pre[i] < suf[i])
ans++;
}
// Print the answer
cout << ans;
}
// Driver Code
int main()
{
int arr[] = { 2, 3, 4, 8, 1, 4 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
count(arr, N);
return 0;
}
Java
// Java program for the above approach
public class gfg
{
// Function to print the count of indices
// in which the maximum in prefix arrays
// is less than that in the suffix array
static void count(int a[], int n)
{
// If size of array is 1
if (n == 1)
{
System.out.print(0);
return;
}
// pre[]: Prefix array
// suf[]: Suffix array
int[] pre = new int[n - 1];
int[] suf = new int[n - 1];
int max = a[0];
// Stores the required count
int ans = 0, i;
pre[0] = a[0];
// Find the maximum in prefix array
for(i = 1; i < n - 1; i++)
{
if (a[i] > max)
max = a[i];
pre[i] = max;
}
max = a[n - 1];
suf[n - 2] = a[n - 1];
// Find the maximum in suffix array
for(i = n - 2; i >= 1; i--)
{
if (a[i] > max)
max = a[i];
suf[i - 1] = max;
}
// Traverse the array
for(i = 0; i < n - 1; i++)
{
// If maximum in prefix array
// is less than maximum in
// the suffix array
if (pre[i] < suf[i])
ans++;
}
// Print the answer
System.out.print(ans);
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 2, 3, 4, 8, 1, 4 };
int N = arr.length;
// Function Call
count(arr, N);
}
}
// This code is contributed by divyesh072019.
Python3
# Python program for the above approach # Function to print the count of indices # in which the maximum in prefix arrays # is less than that in the suffix array def count(a, n) : # If size of array is 1 if (n == 1) : print(0) return # pre[]: Prefix array # suf[]: Suffix array pre = [0] * (n - 1) suf = [0] * (n - 1) max = a[0] # Stores the required count ans = 0 pre[0] = a[0] # Find the maximum in prefix array for i in range(n-1): if (a[i] > max): max = a[i] pre[i] = max max = a[n - 1] suf[n - 2] = a[n - 1] # Find the maximum in suffix array for i in range(n-2, 0, -1): if (a[i] > max): max = a[i] suf[i - 1] = max # Traverse the array for i in range(n - 1): # If maximum in prefix array # is less than maximum in # the suffix array if (pre[i] < suf[i]) : ans += 1 # Print the answer print(ans) # Driver Code arr = [ 2, 3, 4, 8, 1, 4 ] N = len(arr) # Function Call count(arr, N) # This code is contributed by code_hunt.
C#
// C# program for the above approach
using System;
class GFG{
// Function to print the count of indices
// in which the maximum in prefix arrays
// is less than that in the suffix array
static void count(int[] a, int n)
{
// If size of array is 1
if (n == 1)
{
Console.Write(0);
return;
}
// pre[]: Prefix array
// suf[]: Suffix array
int[] pre = new int[n - 1];
int[] suf = new int[n - 1];
int max = a[0];
// Stores the required count
int ans = 0, i;
pre[0] = a[0];
// Find the maximum in prefix array
for(i = 1; i < n - 1; i++)
{
if (a[i] > max)
max = a[i];
pre[i] = max;
}
max = a[n - 1];
suf[n - 2] = a[n - 1];
// Find the maximum in suffix array
for(i = n - 2; i >= 1; i--)
{
if (a[i] > max)
max = a[i];
suf[i - 1] = max;
}
// Traverse the array
for(i = 0; i < n - 1; i++)
{
// If maximum in prefix array
// is less than maximum in
// the suffix array
if (pre[i] < suf[i])
ans++;
}
// Print the answer
Console.Write(ans);
}
// Driver code
static void Main()
{
int[] arr = { 2, 3, 4, 8, 1, 4 };
int N = arr.Length;
// Function Call
count(arr, N);
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// Javascript program for the above approach
// Function to print the count of indices
// in which the maximum in prefix arrays
// is less than that in the suffix array
function count(a, n)
{
// If size of array is 1
if (n == 1)
{
document.write(0);
return;
}
// pre[]: Prefix array
// suf[]: Suffix array
let pre = new Array(n - 1);
let suf = new Array(n - 1);
let max = a[0];
// Stores the required count
let ans = 0, i;
pre[0] = a[0];
// Find the maximum in prefix array
for(i = 1; i < n - 1; i++)
{
if (a[i] > max)
max = a[i];
pre[i] = max;
}
max = a[n - 1];
suf[n - 2] = a[n - 1];
// Find the maximum in suffix array
for(i = n - 2; i >= 1; i--)
{
if (a[i] > max)
max = a[i];
suf[i - 1] = max;
}
// Traverse the array
for(i = 0; i < n - 1; i++)
{
// If maximum in prefix array
// is less than maximum in
// the suffix array
if (pre[i] < suf[i])
ans++;
}
// Print the answer
document.write(ans);
}
let arr = [ 2, 3, 4, 8, 1, 4 ];
let N = arr.length;
// Function Call
count(arr, N);
// This code is contributed by suresh07.
</script>
Producción:
3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por varuntak22 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA