Dada una array arr[] y un entero K , la tarea es encontrar el máximo para todos y cada uno de los subarreglos contiguos de tamaño K .
Ejemplos:
Entrada: arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}, K = 3
Salida: 3 3 4 5 5 5 6
Explicación :
máximo de 1, 2, 3 es 3
máximo de 2, 3, 1 es 3
Máximo de 3, 1, 4 es 4
Máximo de 1, 4, 5 es 5
Máximo de 4, 5, 2 es 5
Máximo de 5, 2, 3 es 5
Máximo de 2, 3, 6 es 6Entrada: arr[] = {8, 5, 10, 7, 9, 4, 15, 12, 90, 13}, K = 4
Salida: 10 10 10 15 15 90 90
Explicación:
El máximo de los primeros 4 elementos es 10, de manera similar para los siguientes 4
elementos (es decir, del índice 1 al 4) es 10, por lo que la secuencia
generada es 10 10 10 15 15 90 90
Enfoque :
la idea es utilizar el árbol de segmentos para responder al máximo de todos los subarreglos de tamaño K.
- Representación de árboles de segmentos
- Los Nodes hoja son los elementos de la array de entrada.
- Cada Node interno representa el máximo de todos sus hijos.
- Construcción del árbol de segmentos a partir de la array dada:
- Empezamos con un segmento arr[0 . . . n-1], y cada vez que dividimos el segmento actual en dos mitades (si aún no se ha convertido en un segmento de longitud 1), y luego llamamos al mismo procedimiento en ambas mitades, y para cada uno de esos segmentos, almacenamos el máximo valor en un Node de árbol de segmento.
- Todos los niveles del árbol de segmentos construido se llenarán por completo excepto el último nivel. Además, el árbol será un árbol binario completo porque siempre dividimos los segmentos en dos mitades en cada nivel.
- Dado que el árbol construido es siempre un árbol binario completo con n hojas, habrá n – 1 Nodes internos. Entonces el total de Nodes será 2 * n – 1.
- La altura del árbol de segmentos será log 2 n .
- Dado que el árbol se representa mediante una array y se debe mantener la relación entre los índices principales y secundarios, el tamaño de la memoria asignada para el árbol de segmentos será 2 *(2 ceil(log 2 n) )-1 .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to answer Maximum
// of allsubarrays of size k
// using segment tree
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000000
// Size of segment
// tree = 2^{log(MAX)+1}
int st[3 * MAX];
// A utility function to get the
// middle index of given range.
int getMid(int s, int e)
{
return s + (e - s) / 2;
}
// A recursive function that
// constructs Segment Tree for
// array[s...e]. node is index
// of current node in segment
// tree st
void constructST(int node, int s,
int e, int arr[])
{
// If there is one element in
// array, store it in current
// node of segment tree and return
if (s == e) {
st[node] = arr[s];
return;
}
// If there are more than
// one elements, then recur
// for left and right subtrees
// and store the max of
// values in this node
int mid = getMid(s, e);
constructST(2 * node, s,
mid, arr);
constructST(2 * node + 1,
mid + 1, e,
arr);
st[node] = max(st[2 * node],
st[2 * node + 1]);
}
/* A recursive function to get the
maximum of range[l, r] The
following parameters for
this function:
st -> Pointer to segment tree
node -> Index of current node in
the segment tree .
s & e -> Starting and ending indexes
of the segment represented
by current node, i.e., st[node]
l & r -> Starting and ending indexes
of range query
*/
int getMax(int node, int s,
int e, int l,
int r)
{
// If segment of this node
// does not belong to
// given range
if (s > r || e < l)
return INT_MIN;
// If segment of this node
// is completely part of
// given range, then return
// the max of segment
if (s >= l && e <= r)
return st[node];
// If segment of this node
// is partially the part
// of given range
int mid = getMid(s, e);
return max(getMax(2 * node,
s, mid,
l, r),
getMax(2 * node + 1,
mid + 1, e,
l, r));
}
// Function to print the max
// of all subarrays of size k
void printKMax(int n, int k)
{
for (int i = 0; i < n; i++) {
if ((k - 1 + i) < n)
cout << getMax(1, 0, n - 1,
i, k - 1 + i)
<< " ";
else
break;
}
}
// Driver code
int main()
{
int k = 4;
int arr[] = { 8, 5, 10, 7, 9, 4, 15,
12, 90, 13 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function to construct the
// segment tree
constructST(1, 0, n - 1, arr);
printKMax(n, k);
return 0;
}
Java
// Java program to answer Maximum
// of allsubarrays of size k
// using segment tree
import java.io.*;
import java.util.*;
class GFG{
static int MAX = 1000000;
// Size of segment
// tree = 2^{log(MAX)+1}
static int[] st = new int[3 * MAX];
// A utility function to get the
// middle index of given range.
static int getMid(int s, int e)
{
return s + (e - s) / 2;
}
// A recursive function that
// constructs Segment Tree for
// array[s...e]. node is index
// of current node in segment
// tree st
static void constructST(int node, int s,
int e, int[] arr)
{
// If there is one element in
// array, store it in current
// node of segment tree and return
if (s == e)
{
st[node] = arr[s];
return;
}
// If there are more than
// one elements, then recur
// for left and right subtrees
// and store the max of
// values in this node
int mid = getMid(s, e);
constructST(2 * node, s, mid, arr);
constructST(2 * node + 1,
mid + 1, e, arr);
st[node] = Math.max(st[2 * node],
st[2 * node + 1]);
}
/* A recursive function to get the
maximum of range[l, r] The
following parameters for
this function:
st -> Pointer to segment tree
node -> Index of current node in
the segment tree .
s & e -> Starting and ending indexes
of the segment represented
by current node, i.e., st[node]
l & r -> Starting and ending indexes
of range query
*/
static int getMax(int node, int s, int e,
int l, int r)
{
// If segment of this node
// does not belong to
// given range
if (s > r || e < l)
return Integer.MIN_VALUE;
// If segment of this node
// is completely part of
// given range, then return
// the max of segment
if (s >= l && e <= r)
return st[node];
// If segment of this node
// is partially the part
// of given range
int mid = getMid(s, e);
return Math.max(getMax(2 * node, s,
mid, l, r),
getMax(2 * node + 1,
mid + 1, e, l, r));
}
// Function to print the max
// of all subarrays of size k
static void printKMax(int n, int k)
{
for(int i = 0; i < n; i++)
{
if ((k - 1 + i) < n)
System.out.print(getMax(1, 0, n - 1,
i, k - 1 + i) + " ");
else
break;
}
}
// Driver code
public static void main(String[] args)
{
int k = 4;
int[] arr = { 8, 5, 10, 7, 9,
4, 15, 12, 90, 13 };
int n = arr.length;
// Function to construct the
// segment tree
constructST(1, 0, n - 1, arr);
printKMax(n, k);
}
}
// This code is contributed by akhilsaini
Python3
# Python3 program to answer maximum
# of all subarrays of size k
# using segment tree
import sys
MAX = 1000000
# Size of segment
# tree = 2^{log(MAX)+1}
st = [0] * (3 * MAX)
# A utility function to get the
# middle index of given range.
def getMid(s, e):
return s + (e - s) // 2
# A recursive function that
# constructs Segment Tree for
# array[s...e]. node is index
# of current node in segment
# tree st
def constructST(node, s, e, arr):
# If there is one element in
# array, store it in current
# node of segment tree and return
if (s == e):
st[node] = arr[s]
return
# If there are more than
# one elements, then recur
# for left and right subtrees
# and store the max of
# values in this node
mid = getMid(s, e)
constructST(2 * node, s, mid, arr)
constructST(2 * node + 1, mid + 1, e, arr)
st[node] = max(st[2 * node], st[2 * node + 1])
''' A recursive function to get the
maximum of range[l, r] The
following parameters for
this function:
st -> Pointer to segment tree
node -> Index of current node in
the segment tree .
s & e -> Starting and ending indexes
of the segment represented
by current node, i.e., st[node]
l & r -> Starting and ending indexes
of range query
'''
def getMax(node, s, e, l, r):
# If segment of this node
# does not belong to
# given range
if (s > r or e < l):
return (-sys.maxsize - 1)
# If segment of this node
# is completely part of
# given range, then return
# the max of segment
if (s >= l and e <= r):
return st[node]
# If segment of this node
# is partially the part
# of given range
mid = getMid(s, e)
return max(getMax(2 * node, s, mid, l, r),
getMax(2 * node + 1, mid + 1, e, l, r))
# Function to print the max
# of all subarrays of size k
def printKMax(n, k):
for i in range(n):
if ((k - 1 + i) < n):
print(getMax(1, 0, n - 1, i,
k - 1 + i), end = " ")
else:
break
# Driver code
if __name__ == "__main__":
k = 4
arr = [ 8, 5, 10, 7, 9, 4, 15, 12, 90, 13 ]
n = len(arr)
# Function to construct the
# segment tree
constructST(1, 0, n - 1, arr)
printKMax(n, k)
# This code is contributed by chitranayal
C#
// C# program to answer Maximum
// of allsubarrays of size k
// using segment tree
using System;
class GFG{
static int MAX = 1000000;
// Size of segment
// tree = 2^{log(MAX)+1}
static int[] st = new int[3 * MAX];
// A utility function to get the
// middle index of given range.
static int getMid(int s, int e)
{
return s + (e - s) / 2;
}
// A recursive function that
// constructs Segment Tree for
// array[s...e]. node is index
// of current node in segment
// tree st
static void constructST(int node, int s,
int e, int[] arr)
{
// If there is one element in
// array, store it in current
// node of segment tree and return
if (s == e)
{
st[node] = arr[s];
return;
}
// If there are more than
// one elements, then recur
// for left and right subtrees
// and store the max of
// values in this node
int mid = getMid(s, e);
constructST(2 * node, s, mid, arr);
constructST(2 * node + 1, mid + 1, e, arr);
st[node] = Math.Max(st[2 * node],
st[2 * node + 1]);
}
/* A recursive function to get the
maximum of range[l, r] The
following parameters for
this function:
st -> Pointer to segment tree
node -> Index of current node in
the segment tree .
s & e -> Starting and ending indexes
of the segment represented
by current node, i.e., st[node]
l & r -> Starting and ending indexes
of range query
*/
static int getMax(int node, int s, int e,
int l, int r)
{
// If segment of this node
// does not belong to
// given range
if (s > r || e < l)
return int.MinValue;
// If segment of this node
// is completely part of
// given range, then return
// the max of segment
if (s >= l && e <= r)
return st[node];
// If segment of this node
// is partially the part
// of given range
int mid = getMid(s, e);
return Math.Max(getMax(2 * node, s,
mid, l, r),
getMax(2 * node + 1,
mid + 1, e, l, r));
}
// Function to print the max
// of all subarrays of size k
static void printKMax(int n, int k)
{
for(int i = 0; i < n; i++)
{
if ((k - 1 + i) < n)
Console.Write(getMax(1, 0, n - 1,
i, k - 1 + i) + " ");
else
break;
}
}
// Driver code
public static void Main()
{
int k = 4;
int[] arr = { 8, 5, 10, 7, 9,
4, 15, 12, 90, 13 };
int n = arr.Length;
// Function to construct the
// segment tree
constructST(1, 0, n - 1, arr);
printKMax(n, k);
}
}
// This code is contributed by akhilsaini
Javascript
<script>
// Javascript program to answer Maximum
// of allsubarrays of size k
// using segment tree
var MAX = 1000000;
// Size of segment
// tree = 2^{log(MAX)+1}
var st = Array(3*MAX);
// A utility function to get the
// middle index of given range.
function getMid(s, e)
{
return s + parseInt((e - s) / 2);
}
// A recursive function that
// constructs Segment Tree for
// array[s...e]. node is index
// of current node in segment
// tree st
function constructST(node, s, e, arr)
{
// If there is one element in
// array, store it in current
// node of segment tree and return
if (s == e) {
st[node] = arr[s];
return;
}
// If there are more than
// one elements, then recur
// for left and right subtrees
// and store the max of
// values in this node
var mid = getMid(s, e);
constructST(2 * node, s,
mid, arr);
constructST(2 * node + 1,
mid + 1, e,
arr);
st[node] = Math.max(st[2 * node],
st[2 * node + 1]);
}
/* A recursive function to get the
maximum of range[l, r] The
following parameters for
this function:
st -> Pointer to segment tree
node -> Index of current node in
the segment tree .
s & e -> Starting and ending indexes
of the segment represented
by current node, i.e., st[node]
l & r -> Starting and ending indexes
of range query
*/
function getMax(node, s, e, l, r)
{
// If segment of this node
// does not belong to
// given range
if (s > r || e < l)
return -1000000000;
// If segment of this node
// is completely part of
// given range, then return
// the max of segment
if (s >= l && e <= r)
return st[node];
// If segment of this node
// is partially the part
// of given range
var mid = getMid(s, e);
return Math.max(getMax(2 * node,
s, mid,
l, r),
getMax(2 * node + 1,
mid + 1, e,
l, r));
}
// Function to print the max
// of all subarrays of size k
function printKMax(n, k)
{
for (var i = 0; i < n; i++) {
if ((k - 1 + i) < n)
document.write( getMax(1, 0, n - 1,
i, k - 1 + i)
+ " ");
else
break;
}
}
// Driver code
var k = 4;
var arr = [8, 5, 10, 7, 9, 4, 15,
12, 90, 13];
var n = arr.length;
// Function to construct the
// segment tree
constructST(1, 0, n - 1, arr);
printKMax(n, k);
</script>
Producción:
10 10 10 15 15 90 90
Complejidad de tiempo: O(N * log K)
Artículo relacionado: Máximo de ventana deslizante (Máximo de todos los subarreglos de tamaño k)
Tema relacionado: Árbol de segmentos
Publicación traducida automáticamente
Artículo escrito por saurabhshadow y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA