Dada una array binaria de tamaño N y un rango en [l, r] , la tarea es encontrar la distancia máxima entre dos 1 en este rango dado.
Ejemplos:
Entrada: arr = {1, 0, 0, 1}, l = 0, r = 3
Salida: 3
En el rango dado de 0 a 3, el primer 1 se encuentra en el índice 0 y el último en el índice 3.
Por lo tanto, la distancia máxima = 3 – 0 = 3.Entrada: arr = {1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0}, l = 3, r = 9
Salida: 6
Enfoque: Crearemos un árbol de segmentos para resolver esto.
- Cada Node en el árbol de segmentos tendrá el índice de 1 más a la izquierda y 1 más a la derecha y un número entero que contiene la distancia máxima entre cualquier elemento con valor 1 en un subarreglo {l, r}.
- Ahora, en este árbol de segmentos podemos fusionar los Nodes izquierdo y derecho como se muestra a continuación:
- Si el Node izquierdo no es válido, devuelva el Node derecho.
- Si el Node derecho no es válido, devuelva el Node izquierdo.
- Un Node es válido si contiene al menos un 0 o al menos un 1.
- Si los Nodes izquierdo y derecho son válidos, entonces:
Sea,- l1 = índice más a la izquierda de 1 (-1 si 0 no existe en ese intervalo)
- r1 = índice más a la derecha de 1 (-1 si 0 no existe en ese intervalo)
- max1 = distancia máxima entre dos 1
- El valor de max1 en el Node fusionado será el valor máximo de max1 en el Node izquierdo y derecho, y la diferencia entre el índice más a la derecha de 1 en el Node derecho y el índice más a la izquierda de 1 en el Node izquierdo.
- El valor de l1 en el Node fusionado será l1 del Node izquierdo si no es -1, de lo contrario l1 del Node derecho.
- El valor de r1 en el Node fusionado será r1 del Node derecho si no es -1, de lo contrario r1 del Node izquierdo.
- Luego, finalmente, para encontrar la respuesta, solo necesitamos llamar a la función de consulta para el rango dado {l, r}.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the maximum
// distance between two elements
// with value 1 within a subarray (l, r)
#include <bits/stdc++.h>
using namespace std;
// Structure for each node
// in the segment tree
struct node {
int l1, r1;
int max1;
} seg[100001];
// A utility function for
// merging two nodes
node task(node l, node r)
{
node x;
x.l1 = (l.l1 != -1) ? l.l1 : r.l1;
x.r1 = (r.r1 != -1) ? r.r1 : l.r1;
x.max1 = max(l.max1, r.max1);
if (l.l1 != -1 && r.r1 != -1)
x.max1 = max(x.max1, r.r1 - l.l1);
return x;
}
// A recursive function that constructs
// Segment Tree for given string
void build(int qs, int qe, int ind, int arr[])
{
// If start is equal to end then
// insert the array element
if (qs == qe) {
if (arr[qs] == 1) {
seg[ind].l1 = seg[ind].r1 = qs;
seg[ind].max1 = INT_MIN;
}
else {
seg[ind].l1 = seg[ind].r1 = -1;
seg[ind].max1 = INT_MIN;
}
return;
}
int mid = (qs + qe) >> 1;
// Build the segment tree
// for range qs to mid
build(qs, mid, ind << 1, arr);
// Build the segment tree
// for range mid+1 to qe
build(mid + 1, qe, ind << 1 | 1, arr);
// merge the two child nodes
// to obtain the parent node
seg[ind] = task(
seg[ind << 1],
seg[ind << 1 | 1]);
}
// Query in a range qs to qe
node query(int qs, int qe,
int ns, int ne, int ind)
{
node x;
x.l1 = x.r1 = -1;
x.max1 = INT_MIN;
// If the range lies in this segment
if (qs <= ns && qe >= ne)
return seg[ind];
// If the range is out of the bounds
// of this segment
if (ne < qs || ns > qe || ns > ne)
return x;
// Else query for the right and left
// child node of this subtree
// and merge them
int mid = (ns + ne) >> 1;
node l = query(qs, qe, ns,
mid, ind << 1);
node r = query(qs, qe,
mid + 1, ne,
ind << 1 | 1);
x = task(l, r);
return x;
}
// Driver code
int main()
{
int arr[] = { 1, 1, 0,
1, 0, 1,
0, 1, 0,
1, 0, 1,
1, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
int l = 3, r = 9;
// Build the segment tree
build(0, n - 1, 1, arr);
// Query in range 3 to 9
node ans = query(l, r, 0, n - 1, 1);
cout << ans.max1 << "\n";
return 0;
}
Java
// Java program to find the maximum
// distance between two elements
// with value 1 within a subarray (l, r)
import java.util.*;
class GFG{
// Structure for each node
// in the segment tree
static class node {
int l1, r1;
int max1;
}
static node []seg = new node[100001];
// A utility function for
// merging two nodes
static node task(node l, node r)
{
node x = new node();
x.l1 = (l.l1 != -1) ? l.l1 : r.l1;
x.r1 = (r.r1 != -1) ? r.r1 : l.r1;
x.max1 = Math.max(l.max1, r.max1);
if (l.l1 != -1 && r.r1 != -1)
x.max1 = Math.max(x.max1, r.r1 - l.l1);
return x;
}
// A recursive function that constructs
// Segment Tree for given String
static void build(int qs, int qe, int ind, int arr[])
{
// If start is equal to end then
// insert the array element
if (qs == qe) {
if (arr[qs] == 1) {
seg[ind].l1 = seg[ind].r1 = qs;
seg[ind].max1 = Integer.MIN_VALUE;
}
else {
seg[ind].l1 = seg[ind].r1 = -1;
seg[ind].max1 = Integer.MIN_VALUE;
}
return;
}
int mid = (qs + qe) >> 1;
// Build the segment tree
// for range qs to mid
build(qs, mid, ind << 1, arr);
// Build the segment tree
// for range mid+1 to qe
build(mid + 1, qe, ind << 1 | 1, arr);
// merge the two child nodes
// to obtain the parent node
seg[ind] = task(
seg[ind << 1],
seg[ind << 1 | 1]);
}
// Query in a range qs to qe
static node query(int qs, int qe,
int ns, int ne, int ind)
{
node x = new node();
x.l1 = x.r1 = -1;
x.max1 = Integer.MIN_VALUE;
// If the range lies in this segment
if (qs <= ns && qe >= ne)
return seg[ind];
// If the range is out of the bounds
// of this segment
if (ne < qs || ns > qe || ns > ne)
return x;
// Else query for the right and left
// child node of this subtree
// and merge them
int mid = (ns + ne) >> 1;
node l = query(qs, qe, ns,
mid, ind << 1);
node r = query(qs, qe,
mid + 1, ne,
ind << 1 | 1);
x = task(l, r);
return x;
}
// Driver code
public static void main(String[] args)
{
for(int i= 0; i < 100001; i++)
seg[i] = new node();
int arr[] = { 1, 1, 0,
1, 0, 1,
0, 1, 0,
1, 0, 1,
1, 0 };
int n = arr.length;
int l = 3, r = 9;
// Build the segment tree
build(0, n - 1, 1, arr);
// Query in range 3 to 9
node ans = query(l, r, 0, n - 1, 1);
System.out.print(ans.max1+ "\n");
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to find the maximum # distance between two elements # with value 1 within a subarray (l, r) import sys # Structure for each node # in the segment tree class node(): def __init__(self): self.l1 = 0 self.r1 = 0 self.max1 = 0 seg = [node() for i in range(100001)] # A utility function for # merging two nodes def task(l, r): x = node() x.l1 = l.l1 if (l.l1 != -1) else r.l1 x.r1 = r.r1 if (r.r1 != -1) else l.r1 x.max1 = max(l.max1, r.max1) # If both the nodes are valid if (l.r1 != -1 and r.l1 != -1): x.max1 = max(x.max1, r.r1 - l.l1) return x # A recursive function that constructs # Segment Tree for given string def build(qs, qe, ind, arr): # If start is equal to end then # insert the array element if (qs == qe): if (arr[qs] == 1): seg[ind].l1 = seg[ind].r1 = qs seg[ind].max1 = -sys.maxsize else: seg[ind].l1 = seg[ind].r1 = -1 seg[ind].max1 = -sys.maxsize return mid = (qs + qe) >> 1 # Build the segment tree # for range qs to mid build(qs, mid, ind << 1, arr) # Build the segment tree # for range mid+1 to qe build(mid + 1, qe, ind << 1 | 1, arr) # Merge the two child nodes # to obtain the parent node seg[ind] = task(seg[ind << 1], seg[ind << 1 | 1]) # Query in a range qs to qe def query(qs, qe, ns, ne, ind): x = node() x.l1 = x.r1 = -1 x.max1 = -sys.maxsize # If the range lies in this segment if (qs <= ns and qe >= ne): return seg[ind] # If the range is out of the bounds # of this segment if (ne < qs or ns > qe or ns > ne): return x # Else query for the right and left # child node of this subtree # and merge them mid = (ns + ne) >> 1 l = query(qs, qe, ns, mid, ind << 1) r = query(qs, qe, mid + 1, ne, ind << 1 | 1) x = task(l, r) return x # Driver code if __name__=="__main__": arr = [ 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0 ] n = len(arr) l = 3 r = 9 # Build the segment tree build(0, n - 1, 1, arr) # Query in range 3 to 9 ans = query(l, r, 0, n - 1, 1) print(ans.max1) # This code is contributed by rutvik_56
C#
// C# program to find the maximum
// distance between two elements
// with value 1 within a subarray (l, r)
using System;
class GFG{
// Structure for each node
// in the segment tree
class node {
public int l1, r1;
public int max1;
}
static node []seg = new node[100001];
// A utility function for
// merging two nodes
static node task(node l, node r)
{
node x = new node();
x.l1 = (l.l1 != -1) ? l.l1 : r.l1;
x.r1 = (r.r1 != -1) ? r.r1 : l.r1;
x.max1 = Math.Max(l.max1, r.max1);
if (l.l1 != -1 && r.r1 != -1)
x.max1 = Math.Max(x.max1, r.r1 - l.l1);
return x;
}
// A recursive function that constructs
// Segment Tree for given String
static void build(int qs, int qe, int ind, int []arr)
{
// If start is equal to end then
// insert the array element
if (qs == qe) {
if (arr[qs] == 1) {
seg[ind].l1 = seg[ind].r1 = qs;
seg[ind].max1 = int.MinValue;
}
else {
seg[ind].l1 = seg[ind].r1 = -1;
seg[ind].max1 = int.MinValue;
}
return;
}
int mid = (qs + qe) >> 1;
// Build the segment tree
// for range qs to mid
build(qs, mid, ind << 1, arr);
// Build the segment tree
// for range mid+1 to qe
build(mid + 1, qe, ind << 1 | 1, arr);
// merge the two child nodes
// to obtain the parent node
seg[ind] = task(
seg[ind << 1],
seg[ind << 1 | 1]);
}
// Query in a range qs to qe
static node query(int qs, int qe,
int ns, int ne, int ind)
{
node x = new node();
x.l1 = x.r1 = -1;
x.max1 = int.MinValue;
// If the range lies in this segment
if (qs <= ns && qe >= ne)
return seg[ind];
// If the range is out of the bounds
// of this segment
if (ne < qs || ns > qe || ns > ne)
return x;
// Else query for the right and left
// child node of this subtree
// and merge them
int mid = (ns + ne) >> 1;
node l = query(qs, qe, ns,
mid, ind << 1);
node r = query(qs, qe,
mid + 1, ne,
ind << 1 | 1);
x = task(l, r);
return x;
}
// Driver code
public static void Main(String[] args)
{
for(int i = 0; i < 100001; i++)
seg[i] = new node();
int []arr = { 1, 1, 0,
1, 0, 1,
0, 1, 0,
1, 0, 1,
1, 0 };
int n = arr.Length;
int l = 3, r = 9;
// Build the segment tree
build(0, n - 1, 1, arr);
// Query in range 3 to 9
node ans = query(l, r, 0, n - 1, 1);
Console.Write(ans.max1+ "\n");
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// JavaScript program to find the maximum
// distance between two elements
// with value 1 within a subarray (l, r)
// Structure for each node
// in the segment tree
class node {
constructor()
{
this.l1 = 0;
this.r1 = 0;
this.max1 =0;
}
}
var seg = Array(100001);
// A utility function for
// merging two nodes
function task(l, r)
{
var x = new node();
x.l1 = (l.l1 != -1) ? l.l1 : r.l1;
x.r1 = (r.r1 != -1) ? r.r1 : l.r1;
x.max1 = Math.max(l.max1, r.max1);
if (l.l1 != -1 && r.r1 != -1)
x.max1 = Math.max(x.max1, r.r1 - l.l1);
return x;
}
// A recursive function that constructs
// Segment Tree for given String
function build(qs, qe, ind, arr)
{
// If start is equal to end then
// insert the array element
if (qs == qe) {
if (arr[qs] == 1) {
seg[ind].l1 = seg[ind].r1 = qs;
seg[ind].max1 = -1000000000;
}
else {
seg[ind].l1 = seg[ind].r1 = -1;
seg[ind].max1 = -1000000000;
}
return;
}
var mid = (qs + qe) >> 1;
// Build the segment tree
// for range qs to mid
build(qs, mid, ind << 1, arr);
// Build the segment tree
// for range mid+1 to qe
build(mid + 1, qe, ind << 1 | 1, arr);
// merge the two child nodes
// to obtain the parent node
seg[ind] = task(
seg[ind << 1],
seg[ind << 1 | 1]);
}
// Query in a range qs to qe
function query(qs, qe, ns, ne, ind)
{
var x = new node();
x.l1 = x.r1 = -1;
x.max1 = -1000000000;
// If the range lies in this segment
if (qs <= ns && qe >= ne)
return seg[ind];
// If the range is out of the bounds
// of this segment
if (ne < qs || ns > qe || ns > ne)
return x;
// Else query for the right and left
// child node of this subtree
// and merge them
var mid = (ns + ne) >> 1;
var l = query(qs, qe, ns,
mid, ind << 1);
var r = query(qs, qe,
mid + 1, ne,
ind << 1 | 1);
x = task(l, r);
return x;
}
// Driver code
for(var i = 0; i < 100001; i++)
seg[i] = new node();
var arr = [1, 1, 0,
1, 0, 1,
0, 1, 0,
1, 0, 1,
1, 0];
var n = arr.length;
var l = 3, r = 9;
// Build the segment tree
build(0, n - 1, 1, arr);
// Query in range 3 to 9
var ans = query(l, r, 0, n - 1, 1);
document.write(ans.max1+ "<br>");
</script>
Producción:
6
Publicación traducida automáticamente
Artículo escrito por muskan_garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA