Dada una array arr[] que consta de N enteros ( inicialmente establecida en 0 ) y una array Q[] , que consta de consultas de la forma {l, r, k} , la tarea para cada consulta es agregar K a los índices l a r (ambos inclusive). Después de realizar todas las consultas, devuelva el elemento máximo presente en la array .
Ejemplo:
Entrada: N =10, q [] = {{1, 5, 3}, {4, 8, 7}, {6, 9, 1}}
Salida: 10
Explicación:
Inicialmente la array es → [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Consulta1 {1, 5, 3} da como resultado [3, 3, 3, 3, 3, 0, 0, 0, 0, 0]
Consulta2 {4 , 8, 7} da como resultado [3, 3, 3, 10, 10, 7, 7, 7, 0, 0]
Consulta2 {6, 9, 1} da como resultado [3, 3, 3, 10, 10, 8 , 8, 8, 1, 0]
Valor máximo en la array actualizada = 10
Enfoque: siga los pasos a continuación para resolver el problema.
- Atraviesa el vector de consultas y para cada consulta {l, r, k}
- Sumar k a a[l] y restar k de a[r+1]
- Inicialice la variable x = 0 para almacenar la suma acumulada y m = INT_MIN para almacenar el valor máximo
- Recorra la array , agregue elementos a x y actualice m.
- Imprimir el valor máximo m
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 find the max sum
// after processing q queries
int max_sum(int a[],
vector<pair<pair<int, int>, int> > v,
int q, int n)
{
// Store the cumulative sum
int x = 0;
// Store the maximum sum
int m = INT_MIN;
// Iterate over the range 0 to q
for (int i = 0; i < q; i++) {
// Variables to extract
// values from vector
int p, q, k;
p = v[i].first.first;
q = v[i].first.second;
k = v[i].second;
a[p] += k;
if (q + 1 <= n)
a[q + 1] -= k;
}
// Iterate over the range [1, n]
for (int i = 1; i <= n; i++)
{
// Calculate cumulative sum
x += a[i];
// Calculate maximum sum
m = max(m, x);
}
// Return the maximum sum after q queries
return m;
}
// Driver code
int main()
{
// Stores the size of array
// and number of queries
int n = 10, q = 3;
// Stores the sum
int a[n + 5] = { 0 };
// Storing input queries
vector<pair<pair<int, int>, int> > v(q);
v[0].first.first = 1;
v[0].first.second = 5;
v[0].second = 3;
v[1].first.first = 4;
v[1].first.second = 8;
v[1].second = 7;
v[2].first.first = 6;
v[2].first.second = 9;
v[2].second = 1;
// Function call to find the maximum sum
cout << max_sum(a, v, q, n);
return 0;
}
Java
// Java program for the above approach
import java.lang.*;
import java.util.*;
class GFG{
// Function to find the max sum
// after processing q queries
static int max_sum(int a[],
ArrayList<ArrayList<Integer>> v,
int q, int n)
{
// Store the cumulative sum
int x = 0;
// Store the maximum sum
int m = Integer.MIN_VALUE;
// Iterate over the range 0 to q
for(int i = 0; i < q; i++)
{
// Variables to extract
// values from vector
int p, qq, k;
p = v.get(i).get(0);
qq = v.get(i).get(1);
k = v.get(i).get(2);
a[p] += k;
if (qq + 1 <= n)
a[qq + 1] -= k;
}
// Iterate over the range [1, n]
for(int i = 1; i <= n; i++)
{
// Calculate cumulative sum
x += a[i];
// Calculate maximum sum
m = Math.max(m, x);
}
// Return the maximum sum after q queries
return m;
}
// Driver code
public static void main(String[] args)
{
// Stores the size of array
// and number of queries
int n = 10, q = 3;
// Stores the sum
int[] a = new int[n + 5];
// Storing input queries
ArrayList<ArrayList<Integer>> v= new ArrayList<>();
for(int i = 0; i < q; i++)
v.add(new ArrayList<>());
v.get(0).add(1);
v.get(0).add(5);
v.get(0).add(3);
v.get(1).add(4);
v.get(1).add(8);
v.get(1).add(7);
v.get(2).add(6);
v.get(2).add(9);
v.get(2).add(1);
// Function call to find the maximum sum
System.out.println(max_sum(a, v, q, n));
}
}
// This code is contributed by offbeat
Python3
# Python program for the above approach # Function to find the max sum # after processing q queries def max_sum(a, v, q, n): # Store the cumulative sum x = 0; # Store the maximum sum m = -10**9; # Iterate over the range 0 to q for i in range(q): # Variables to extract # values from vector p = v[i][0][0]; q = v[i][0][1]; k = v[i][1]; a[p] += k; if (q + 1 <= n): a[q + 1] -= k; # Iterate over the range [1, n] for i in range(1, n + 1): # Calculate cumulative sum x += a[i]; # Calculate maximum sum m = max(m, x); # Return the maximum sum after q queries return m; # Driver code # Stores the size of array # and number of queries n = 10 q = 3; # Stores the sum a = [0] * (n + 5); # Storing input queries v = [[[0 for i in range(2)] for x in range(2)] for z in range(q)] v[0][0][0] = 1; v[0][0][1] = 5; v[0][1] = 3; v[1][0][0] = 4; v[1][0][1] = 8; v[1][1] = 7; v[2][0][0] = 6; v[2][0][1] = 9; v[2][1] = 1; # Function call to find the maximum sum print(max_sum(a, v, q, n)); # This code is contributed by _saurabh_jaiswal
Javascript
<script>
// Javascript program for the above approach
// Function to find the max sum
// after processing q queries
function max_sum(a, v, q, n) {
// Store the cumulative sum
let x = 0;
// Store the maximum sum
let m = Number.MIN_SAFE_INTEGER;
// Iterate over the range 0 to q
for (let i = 0; i < q; i++) {
// Variables to extract
// values from vector
let p, q, k;
p = v[i][0][0];
q = v[i][0][1];
k = v[i][1];
a[p] += k;
if (q + 1 <= n)
a[q + 1] -= k;
}
// Iterate over the range [1, n]
for (let i = 1; i <= n; i++) {
// Calculate cumulative sum
x += a[i];
// Calculate maximum sum
m = Math.max(m, x);
}
// Return the maximum sum after q queries
return m;
}
// Driver code
// Stores the size of array
// and number of queries
let n = 10, q = 3;
// Stores the sum
let a = new Array(n + 5).fill(0);
// Storing input queries
let v = new Array(q).fill(0).map(() => new Array(2).fill(0).map(() => new Array(2).fill(0)));
v[0][0][0] = 1;
v[0][0][1] = 5;
v[0][1] = 3;
v[1][0][0] = 4;
v[1][0][1] = 8;
v[1][1] = 7;
v[2][0][0] = 6;
v[2][0][1] = 9;
v[2][1] = 1;
// Function call to find the maximum sum
document.write(max_sum(a, v, q, n));
// This code is contributed by gfgking.
</script>
Producción:
10
Complejidad de tiempo: O(N+K) donde N es el tamaño de la array y K es un número de consultas
Complejidad de espacio: O(1)