Dada una array arr que contiene N enteros positivos y el número de consultas Q , para cada tarea de consulta es encontrar la suma máxima de pares en el rango de índice dado [L, R] donde L y R son los índices alto y bajo respectivos . Ejemplos:
Entrada: arr = {3, 4, 5, 6, 7, 8}, Q[][2] = [[0, 3], [3, 5]]
Salida:
11
15
Explicación:
Para la primera consulta, subarreglo es [3, 4, 5, 6]
Todos los pares son (3, 4), (3, 5), (3, 6), (4, 5), (4, 6), (5, 6)
Por lo tanto la suma máxima de pares = (5 + 6) = 11
Para la segunda consulta, el subarreglo es [6, 7, 8]
Todos los pares del subarreglo son (6, 7), (6, 8), (7, 8)
Por lo tanto, la suma máxima de pares = (7 + 8) = 15
Enfoque ingenuo: para cada rango de consulta, haga lo siguiente
- Encuentre el máximo y el segundo máximo en el rango de consulta dado.
- La suma del máximo y el segundo máximo será la suma del par máximo del rango dado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find maximum
// pair sum in the given
// index range of an Array
#include <bits/stdc++.h>
using namespace std;
// Node structure to store a query
struct node {
int f;
int s;
};
// Function to find the required sum
void findSum(int* arr, int n,
int Q, node* query)
{
// Run a loop to iterate
// over query array
for (int i = 0; i < Q; i++) {
// declare first 'f'
// and second 's' variables
int f, s;
// Initialise them with 0
f = s = 0;
// Iterate over the
// given array from
// range query[i].f to query[i].s
for (int j = query[i].f;
j <= query[i].s;
j++) {
// If the array element
// value is greater than
// current f, store
// current f in s and
// array element value in f
if (arr[j] >= f) {
s = f;
f = arr[j];
}
// else if element
// is greater than s,
// update s with
// array element value
else if (arr[j] > s)
s = arr[j];
}
// print the sum of f and s
cout << (f + s) << endl;
}
}
// Driver code
int main()
{
// Given array and number of queries
int arr[] = { 3, 4, 5, 6, 7, 8 }, Q = 2;
int n = sizeof(arr) / sizeof(arr[0]);
// Declare and define queries
node query[Q];
query[0] = { 0, 3 };
query[1] = { 3, 5 };
findSum(arr, n, Q, query);
}
Java
// Java program to find maximum
// pair sum in the given
// index range of an Array
class GFG{
// Node structure to store a query
static class node {
int f;
int s;
public node(int f, int s) {
this.f = f;
this.s = s;
}
};
// Function to find the required sum
static void findSum(int []arr, int n,
int Q, node []query)
{
// Run a loop to iterate
// over query array
for (int i = 0; i < Q; i++) {
// declare first 'f'
// and second 's' variables
int f, s;
// Initialise them with 0
f = s = 0;
// Iterate over the
// given array from
// range query[i].f to query[i].s
for (int j = query[i].f;
j <= query[i].s;
j++) {
// If the array element
// value is greater than
// current f, store
// current f in s and
// array element value in f
if (arr[j] >= f) {
s = f;
f = arr[j];
}
// else if element
// is greater than s,
// update s with
// array element value
else if (arr[j] > s)
s = arr[j];
}
// print the sum of f and s
System.out.print((f + s) +"\n");
}
}
// Driver code
public static void main(String[] args)
{
// Given array and number of queries
int arr[] = { 3, 4, 5, 6, 7, 8 }, Q = 2;
int n = arr.length;
// Declare and define queries
node []query = new node[2];
query[0] = new node( 0, 3 );
query[1] = new node(3, 5 );
findSum(arr, n, Q, query);
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python program to find maximum # pair sum in the given # index range of an Array # Node structure to store a query from pickle import NONE class node: def __init__(self, f, s): self.f = f self.s = s # Function to find the required sum def findSum(arr, n, Q, query): # Run a loop to iterate # over query array for i in range(Q): # declare first 'f' # and second 's' variables # Initialise them with 0 f,s = 0,0 # Iterate over the # given array from # range query[i].f to query[i].s for j in range(query[i].f,query[i].s+1): # If the array element # value is greater than # current f, store # current f in s and # array element value in f if (arr[j] >= f): s = f f = arr[j] # else if element # is greater than s, # update s with # array element value elif (arr[j] > s): s = arr[j] # print the sum of f and s print(f + s) # Driver code # Given array and number of queries arr = [ 3, 4, 5, 6, 7, 8 ] Q = 2 n = len(arr) # Declare and define queries query = [None]*Q query[0] = node( 0, 3 ) query[1] = node( 3, 5 ) findSum(arr, n, Q, query) # This code is contributed by shinjanpatra
C#
// C# program to find maximum
// pair sum in the given
// index range of an Array
using System;
class GFG{
// Node structure to store a query
class node {
public int f;
public int s;
public node(int f, int s) {
this.f = f;
this.s = s;
}
};
// Function to find the required sum
static void findSum(int []arr, int n,
int Q, node []query)
{
// Run a loop to iterate
// over query array
for (int i = 0; i < Q; i++) {
// declare first 'f'
// and second 's' variables
int f, s;
// Initialise them with 0
f = s = 0;
// Iterate over the
// given array from
// range query[i].f to query[i].s
for (int j = query[i].f;
j <= query[i].s;
j++) {
// If the array element
// value is greater than
// current f, store
// current f in s and
// array element value in f
if (arr[j] >= f) {
s = f;
f = arr[j];
}
// else if element
// is greater than s,
// update s with
// array element value
else if (arr[j] > s)
s = arr[j];
}
// print the sum of f and s
Console.Write((f + s) +"\n");
}
}
// Driver code
public static void Main(String[] args)
{
// Given array and number of queries
int []arr = { 3, 4, 5, 6, 7, 8 };
int Q = 2;
int n = arr.Length;
// Declare and define queries
node []query = new node[2];
query[0] = new node( 0, 3 );
query[1] = new node(3, 5 );
findSum(arr, n, Q, query);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript program to find maximum
// pair sum in the given
// index range of an Array
// Node structure to store a query
class node {
constructor(f,s) {
this.f = f;
this.s = s;
}
}
// Function to find the required sum
function findSum(arr,n,Q,query)
{
// Run a loop to iterate
// over query array
for (let i = 0; i < Q; i++) {
// declare first 'f'
// and second 's' variables
let f, s;
// Initialise them with 0
f = s = 0;
// Iterate over the
// given array from
// range query[i].f to query[i].s
for (let j = query[i].f;j <= query[i].s;j++) {
// If the array element
// value is greater than
// current f, store
// current f in s and
// array element value in f
if (arr[j] >= f) {
s = f;
f = arr[j];
}
// else if element
// is greater than s,
// update s with
// array element value
else if (arr[j] > s)
s = arr[j];
}
// print the sum of f and s
document.write(f + s,"</br>");
}
}
// Driver code
// Given array and number of queries
let arr = [ 3, 4, 5, 6, 7, 8 ], Q = 2;
let n = arr.length;
// Declare and define queries
let query = new Array(Q);
query[0] = new node( 0, 3 );
query[1] = new node( 3, 5 );
findSum(arr, n, Q, query);
// This code is contributed by shinjanpatra
</script>
Producción:
11 15
Análisis de rendimiento:
- Complejidad de tiempo: en el enfoque anterior, estamos recorriendo la array de longitud N para cada consulta Q. Por lo tanto, la complejidad del tiempo sería O(N*Q) .
- Espacio auxiliar: en el enfoque anterior no se utiliza espacio adicional, por lo tanto, la complejidad del espacio auxiliar será O(1) .
Enfoque eficiente: la idea es utilizar el árbol de segmentos donde cada Node del árbol de segmentos almacena dos valores:
- Máximo del subárbol dado a continuación
- Segundo máximo del subárbol dado a continuación
- Complejidad de tiempo: en el enfoque anterior, estamos construyendo un árbol de segmentos que tiene una complejidad de tiempo O (N). Luego, para cada una de las consultas Q , encontramos la solución en el tiempo O (logN) . Entonces la complejidad del tiempo total es O(N+Q*logN)
- Complejidad del espacio auxiliar: en el enfoque anterior, estamos utilizando espacio adicional para almacenar el árbol de segmentos que ocupa (4 * N + 1) espacio. Entonces la complejidad del espacio auxiliar es O(N)
- Complejidad de tiempo: en el enfoque anterior, estamos construyendo un árbol de segmentos que tiene una complejidad de tiempo O (N). Luego, para cada una de las consultas Q , encontramos la solución en el tiempo O (logN) . Entonces la complejidad del tiempo total es O(N+Q*logN)