Dada una permutación P de primeros N números naturales, la tarea es contar los pares de índices (i, j) tales que P[i] + P[j] = max(P[x]) donde i ≤ x ≤ j .
Ejemplos:
Entrada: P[] = {3, 4, 1, 5, 2}
Salida: 2
Solo los pares de índices válidos son (0, 4) y (0, 2)
Entrada: P[] = {1, 3, 2}
Salida : 1
Enfoque ingenuo: podemos resolver este problema iterando para todos los pares posibles (i, j) y cada vez se obtiene el máximo entre ellos. La complejidad temporal de este enfoque será O(n 3 ) .
Enfoque eficiente: fije el elemento máximo en un segmento e itere sobre los elementos a la izquierda o a la derecha. Si el máximo actual es x, y el elemento que encontramos es y, compruebe si el elemento xy puede formar un subsegmento con y (es decir, x es el valor máximo en el segmento entre y y xy). Esto funciona en O (n * n)
Pero si podemos precalcular los bordes de los segmentos donde x es el elemento máximo y siempre elegimos iterar en la parte más pequeña del segmento, entonces la complejidad del tiempo se reducirá a O (nlogn).
Debido a que cada elemento se procesará no más de logn veces, si lo procesamos en un segmento de tamaño m, la parte más pequeña no contiene más de m/2 elementos (que procesaremos más adelante, y la parte más pequeña de este segmento no contiene más de m/4 elementos, etc.).
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP implementation of the approach
#include<bits/stdc++.h>
using namespace std;
// Function to return the count of
// required index pairs
int Count_Segment(int p[], int n)
{
// To store the required count
int count = 0;
// Array to store the left elements
// upto which current element is maximum
int upto[n + 1];
for(int i = 0; i < n + 1; i++)
upto[i] = 0;
// Iterating through the whole permutation
// except first and last element
int j = 0,curr = 0;
for (int i = 1; i < n + 1; i++)
{
// If current element can be maximum
// in a subsegment
if (p[i] > p[i - 1] and p[i] > p[i + 1])
{
// Current maximum
curr = p[i];
// Iterating for smaller values then
// current maximum on left of it
j = i - 1;
while (j >= 0 and p[j] < curr)
{
// Storing left borders
// of the current maximum
upto[p[j]]= curr;
j -= 1;
}
// Iterating for smaller values then
// current maximum on right of it
j = i + 1;
while (j < n and p[j] < curr)
{
// Condition satisfies
if (upto[curr-p[j]] == curr)
count += 1;
j+= 1;
}
}
}
// Return count of subsegments
return count;
}
// Driver Code
int main()
{
int p[] = {3, 4, 1, 5, 2};
int n = sizeof(p)/sizeof(p[0]);
cout << (Count_Segment(p, n));
return 0;
}
// This code is contributed by
// Surendra_Gangwar
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to return the count of
// required index pairs
static int Count_Segment(int p[], int n)
{
// To store the required count
int count = 0;
// Array to store the left elements
// upto which current element is maximum
int []upto = new int[n + 1];
for(int i = 0; i < n + 1; i++)
upto[i] = 0;
// Iterating through the whole permutation
// except first and last element
int j = 0,curr = 0;
for (int i = 1; i < n ; i++)
{
// If current element can be maximum
// in a subsegment
if (p[i] > p[i - 1] && p[i] > p[i + 1])
{
// Current maximum
curr = p[i];
// Iterating for smaller values then
// current maximum on left of it
j = i - 1;
while (j >= 0 && p[j] < curr)
{
// Storing left borders
// of the current maximum
upto[p[j]]= curr;
j -= 1;
}
// Iterating for smaller values then
// current maximum on right of it
j = i + 1;
while (j < n && p[j] < curr)
{
// Condition satisfies
if (upto[curr-p[j]] == curr)
count += 1;
j+= 1;
}
}
}
// Return count of subsegments
return count;
}
// Driver Code
public static void main(String[] args)
{
int p[] = {3, 4, 1, 5, 2};
int n = p.length;
System.out.println(Count_Segment(p, n));
}
}
/* This code contributed by PrinciRaj1992 */
Python
# Python3 implementation of the approach # Function to return the count of # required index pairs def Count_Segment(p, n): # To store the required count count = 0 # Array to store the left elements # upto which current element is maximum upto = [False]*(n + 1) # Iterating through the whole permutation # except first and last element for i in range(1, n-1): # If current element can be maximum # in a subsegment if p[i]>p[i-1] and p[i]>p[i + 1]: # Current maximum curr = p[i] # Iterating for smaller values then # current maximum on left of it j = i-1 while j>= 0 and p[j]<curr: # Storing left borders # of the current maximum upto[p[j]]= curr j-= 1 # Iterating for smaller values then # current maximum on right of it j = i + 1 while j<n and p[j]<curr: # Condition satisfies if upto[curr-p[j]]== curr: count+= 1 j+= 1 # Return count of subsegments return count # Driver Code if __name__=="__main__": p =[3, 4, 1, 5, 2] n = len(p) print(Count_Segment(p, n))
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the count of
// required index pairs
static int Count_Segment(int []p, int n)
{
// To store the required count
int count = 0;
// Array to store the left elements
// upto which current element is maximum
int []upto = new int[n + 1];
for(int i = 0; i < n + 1; i++)
upto[i] = 0;
// Iterating through the whole permutation
// except first and last element
int j = 0,curr = 0;
for (int i = 1; i < n ; i++)
{
// If current element can be maximum
// in a subsegment
if (p[i] > p[i - 1] && p[i] > p[i + 1])
{
// Current maximum
curr = p[i];
// Iterating for smaller values then
// current maximum on left of it
j = i - 1;
while (j >= 0 && p[j] < curr)
{
// Storing left borders
// of the current maximum
upto[p[j]]= curr;
j= j - 1;
}
// Iterating for smaller values then
// current maximum on right of it
j = i + 1;
while (j < n && p[j] < curr)
{
// Condition satisfies
if (upto[curr-p[j]] == curr)
count += 1;
j= j+ 1;
}
}
}
// Return count of subsegments
return count;
}
// Driver Code
static public void Main ()
{
int []p = {3, 4, 1, 5, 2};
int n = p.Length;
Console.WriteLine(Count_Segment(p, n));
}
}
/* This code contributed by ajit*/
Javascript
<script>
// javascript implementation of the approach
// Function to return the count of
// required index pairs
function Count_Segment(p , n) {
// To store the required count
var count = 0;
// Array to store the left elements
// upto which current element is maximum
var upto = Array(n + 1).fill(0);
for (i = 0; i < n + 1; i++)
upto[i] = 0;
// Iterating through the whole permutation
// except first and last element
var j = 0, curr = 0;
for (i = 1; i < n; i++) {
// If current element can be maximum
// in a subsegment
if (p[i] > p[i - 1] && p[i] > p[i + 1]) {
// Current maximum
curr = p[i];
// Iterating for smaller values then
// current maximum on left of it
j = i - 1;
while (j >= 0 && p[j] < curr) {
// Storing left borders
// of the current maximum
upto[p[j]] = curr;
j -= 1;
}
// Iterating for smaller values then
// current maximum on right of it
j = i + 1;
while (j < n && p[j] < curr) {
// Condition satisfies
if (upto[curr - p[j]] == curr)
count += 1;
j += 1;
}
}
}
// Return count of subsegments
return count;
}
// Driver Code
var p = [ 3, 4, 1, 5, 2 ];
var n = p.length;
document.write(Count_Segment(p, n));
// This code is contributed by todaysgaurav
</script>
2
Complejidad de tiempo: O(N 2 ), donde N representa el tamaño de la array dada.
Espacio auxiliar: O(N), donde N representa el tamaño de la array dada.
Publicación traducida automáticamente
Artículo escrito por saurabh sisodia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA