Dada una array arr[] y un entero k , podemos cortar esta array en k posiciones diferentes donde k[] almacena las posiciones de todos los cortes requeridos. La tarea es imprimir la suma máxima entre todos los cortes después de cada corte realizado.
Cada corte tiene la forma de un entero x donde x denota un corte entre arr[x] y arr[x + 1] .
Ejemplos:
Entrada: arr[] = {4, 5, 6, 7, 8}, k[] = {0, 2, 3, 1}
Salida:
26
15
11
8
Primer corte -> {4} y {5, 6, 7, 8}. La suma máxima posible es 5 + 6 + 7 + 8 = 26
Segundo corte -> {4}, {5, 6} y {7, 8}. Suma máxima = 15
Tercer corte -> {4}, {5, 6}, {7} y {8}. Suma máxima = 11
Cuarto corte -> {4}, {5}, {6}, {7} y {8}. Suma máxima = 8Entrada: arr[] = {1, 2, 3}, k[] = {1}
Salida:
3
Enfoque ingenuo: almacene las piezas resultantes de la array en una ArrayList y, después de cada corte, calcule linealmente la suma máxima posible. Pero este método requeriría tiempo O(n*k) para responder a todas las consultas.
Enfoque eficiente: podemos representar cada pieza resultante de la array como un objeto Piece con los miembros de datos inicio (índice de inicio de esta pieza), fin (índice final de esta pieza) y valor (valor de suma de esta pieza). Podemos almacenar estas piezas en un TreeSet y ordenarlas por sus valores de suma . Por lo tanto, después de cada corte podemos obtener la pieza con mayor valor de suma en O(log(n)).
- Tenemos que hacer una array de suma de prefijos de los valores de la array para obtener la suma entre dos índices en tiempo constante.
- Tenemos que mantener otro TreeSet con índices de inicio de todas las piezas actuales para que podamos encontrar la pieza exacta para cortar. Por ejemplo, para una sola pieza:
- {1, 8} -> inicio = 1, final = 2, valor = 9 y {6, 3, 9} -> inicio = 3, final = 5, valor = 18.
- Para cortar el índice 4, necesitamos cortar la segunda pieza en dos partes como {6, 3} y {9}. Entonces obtenemos el índice de inicio de qué pieza cortar de este TreeSet.
A continuación se muestra la implementación del enfoque anterior:
// Java implementation of the approach
import java.io.IOException;
import java.io.InputStream;
import java.util.*;
// Comparator to sort the Pieces
// based on their sum values
class MyComp implements Comparator<Piece> {
public int compare(Piece p1, Piece p2)
{
if (p2.val != p1.val)
return p2.val - p1.val;
if (p1.start != p2.start)
return p2.start - p1.start;
return 0;
}
}
class Piece {
int start;
int end;
int val;
// Constructor to initialize each Piece
Piece(int s, int e, int v)
{
start = s;
end = e;
val = v;
}
}
class GFG {
// Function to perform the given queries on the array
static void solve(int n, int k, int cuts[], int A[])
{
// Prefix sum array
int sum[] = new int[n];
sum[0] = A[0];
for (int i = 1; i < n; i++)
sum[i] = sum[i - 1] + A[i];
// TreeSet storing all the starts
TreeSet<Integer> t = new TreeSet<>();
// TreeSet storing the actual pieces
TreeSet<Piece> pq = new TreeSet<>(new MyComp());
Piece temp[] = new Piece[n];
temp[0] = new Piece(0, n - 1, sum[n - 1]);
// Added the whole array or Piece of array
// as there is no cuts yet
pq.add(temp[0]);
t.add(0);
for (int i = 0; i < k; i++) {
// curr is the piece to be cut
int curr = t.floor(cuts[i]);
pq.remove(temp[curr]);
int end = temp[curr].end;
// When a piece with start = s and end = e
// is cut at index i, two pieces are created with
// start = s, end = i and start = i + 1 and end = e
// We remove the previous piece and add
// this one to the TreeSet
temp[curr]
= new Piece(curr, cuts[i],
sum[cuts[i]]
- (curr == 0 ? 0 : sum[curr - 1]));
pq.add(temp[curr]);
temp[cuts[i] + 1]
= new Piece(cuts[i] + 1,
end, sum[end] - sum[cuts[i]]);
pq.add(temp[cuts[i] + 1]);
t.add(curr);
t.add(cuts[i] + 1);
System.out.println(pq.first().val);
}
}
// Driver code
public static void main(String[] args)
{
int A[] = { 4, 5, 6, 7, 8 };
int n = A.length;
int cuts[] = { 0, 2, 3, 1 };
int k = cuts.length;
solve(n, k, cuts, A);
}
}
26 15 11 8
Tiempo Complejidad O(n + k Log n)
Publicación traducida automáticamente
Artículo escrito por mayukh Sengupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA