Dada una array arr[] de tamaño N , la tarea es encontrar la diferencia mínima entre la suma máxima y mínima del subarreglo cuando la array dada se divide en 4 subarreglos no vacíos.
Ejemplos:
Entrada: N = 5, arr[] = {3, 2, 4, 1, 2}
Salida: 2
Explicación: Divida la array en cuatro partes como {3}, {2}, {4} y {1, 2} .
La suma de todos los elementos de estas partes es 3, 2, 4 y 3 .
La diferencia entre el máximo y el mínimo es (4 – 2) = 2 .Entrada: N = 4, arr[] = {14, 6, 1, 7}
Salida: 13
Explicación: Divida la array en cuatro partes {14}, {6}, {1} y {7} .
La suma de todos los elementos de estas cuatro partes es 14, 6, 1 y 7 .
La diferencia entre el máximo y el mínimo (14 – 1) = 13 .
Es la única forma posible de dividir la array en 4 partes posibles
Enfoque ingenuo: la forma más sencilla es comprobar todas las combinaciones posibles de tres cortes y, para cada valor posible, comprobar las sumas de los subarreglos. Luego calcula la diferencia mínima entre todas las combinaciones posibles.
Complejidad de Tiempo: O(N 4 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el problema se puede resolver utilizando el concepto de suma de prefijos y dos punteros en función de la siguiente observación:
Para dividir la array en 4 subarreglos , se requieren tres divisiones .
- Si la segunda división es fija (por ejemplo, entre el índice i y i+1 ), habrá una división a la izquierda y otra a la derecha.
- La diferencia se minimizará cuando los dos subarreglos de la izquierda tengan una suma lo más cercana posible y lo mismo para los dos subarreglos del lado derecho de la división.
- La suma total de la parte izquierda y de la parte derecha se puede obtener en tiempo constante con la ayuda del cálculo de la suma de prefijos .
Ahora la división en la parte izquierda y en la parte derecha se puede decidir de manera óptima utilizando la técnica de dos puntos .
- Cuando se fije la segunda división, decida la división izquierda iterando a través de la parte izquierda hasta que la diferencia entre la suma de las dos partes sea mínima.
- Se puede encontrar minimizando la diferencia entre la suma total y el doble de la suma de cualquiera de las partes. [El valor mínimo de esto significa que la diferencia entre ambas partes es mínima]
Haz lo mismo para la parte derecha también.
Siga los pasos a continuación para resolver este problema:
- En primer lugar, calcule previamente la array de suma de prefijos de la array dada.
- Cree tres variables i = 1, j = 2 y k = 3, cada una de las cuales representa los cortes (indexación basada en 1)
- Iterar a través de los posibles valores de j de 2 a N – 1 .
- Para cada valor de j , intente aumentar el valor de i hasta que la diferencia absoluta entre Left_Sum_1 y Left_Sum_2 disminuya y i sea menor que j (Left_Sum_1 y Left_Sum_2 son las sumas de los dos subarreglos de la izquierda).
- Para cada valor de j , intente aumentar el valor de k , hasta que la diferencia absoluta entre Right_Sum_1 y Right_Sum_2 disminuya y k sea menor que N + 1 (Right_Sum_1 y Right_Sum_2 son las sumas de los dos subarreglos de la derecha).
- Utilice la suma de prefijos para calcular directamente los valores de Left_Sum_1 , Left_Sum_2 , Right_Sum_1 y Right_Sum_2 .
- Para cada valor válido de i, j y k , encuentre la diferencia entre el valor máximo y mínimo de la suma de los elementos de estas partes
- El mínimo entre ellos es la respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum difference
// between maximum and minimum subarray sum
// after dividing the array into 4 subarrays
long long int minSum(vector<int>& v, int n)
{
vector<long long int> a(n + 1);
// Precompute the prefix sum
a[0] = 0;
for (int i = 1; i <= n; i++) {
a[i] = a[i - 1] + v[i - 1];
}
// Initialize the ans with large value
long long int ans = 1e18;
// There are total four parts means 3 cuts.
// Here i, j, k represent those 3 cuts
for (int i = 1, j = 2, k = 3; j < n; j++) {
while (i + 1 < j
&& abs(a[j] - 2 * a[i])
> abs(a[j]
- 2 * a[i + 1])) {
i++;
}
while (k + 1 < n
&& abs(a[n] + a[j] - 2 * a[k])
> abs(a[n] + a[j]
- 2 * a[k + 1])) {
k++;
}
ans = min(ans,
max({ a[i], a[j] - a[i],
a[k] - a[j],
a[n] - a[k] })
- min({ a[i], a[j] - a[i],
a[k] - a[j],
a[n] - a[k] }));
}
return ans;
}
// Driver Code
int main()
{
vector<int> arr = { 3, 2, 4, 1, 2 };
int N = arr.size();
// Function call
cout << minSum(arr, N);
return 0;
}
Java
// Java program for the above approach
public class GFG
{
// Function to find the minimum difference
// between maximum and minimum subarray sum
// after dividing the array into 4 subarrays
static int minCost(int arr[], int n)
{
// Precompute the prefix sum
int a[] = new int[n + 1];
a[0] = 0;
for (int i = 1; i <= n; i++) {
a[i] = a[i - 1] + arr[i - 1];
}
// Initialize the ans with large value
int ans = Integer.MAX_VALUE;
// There are total four parts means 3 cuts.
// Here i, j, k represent those 3 cuts
for (int i = 1, j = 2, k = 3; j < n; j++) {
while (i + 1 < j
&& Math.abs(a[j] - 2 * a[i])
> Math.abs(a[j] - 2 * a[i + 1])) {
i++;
}
while (k + 1 < n
&& Math.abs(a[n] + a[j] - 2 * a[k])
> Math.abs(a[n] + a[j]
- 2 * a[k + 1])) {
k++;
}
ans = Math.min(
ans,
Math.max(a[i],
Math.max(a[j] - a[i],
Math.max(a[k] - a[j],
a[n] - a[k])))
- Math.min(
a[i],
Math.min(a[j] - a[i],
Math.min(a[k] - a[j],
a[n] - a[k]))));
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 3, 2, 4, 1, 2 };
int N = arr.length;
System.out.println(minCost(arr, N));
}
}
// This code is contributed by dwivediyash
Python3
# Python3 code to implement the approach # Function to find the minimum difference # between maximum and minimum subarray sum # after dividing the array into 4 subarrays def minSum(v, n): a = [0] # Precompute the prefix sum for i in range(1, n + 1): a.append(a[-1] + v[i - 1]) # Initialize the ans with large value ans = 10 ** 18 # There are total four parts means 3 cuts. # Here i, j, k represent those 3 cuts i = 1 j = 2 k = 3 while (j < n): while (i + 1 < j and abs(a[j] - 2 * a[i]) > abs(a[j] - 2 * a[i + 1])): i += 1 while (k + 1 < n and abs(a[n] + a[j] - 2 * a[k]) > abs(a[n] + a[j] - 2 * a[k + 1])): k += 1 ans = min(ans, max([a[i], a[j] - a[i], a[k] - a[j], a[n] - a[k]] ) - min([a[i], a[j] - a[i], a[k] - a[j], a[n] - a[k]])) j += 1 return ans # Driver Code arr = [3, 2, 4, 1, 2] N = len(arr) # Function call print(minSum(arr, N)) # this code is contributed by phasing17
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the minimum difference
// between maximum and minimum subarray sum
// after dividing the array into 4 subarrays
static int minCost(int[] arr, int n)
{
// Precompute the prefix sum
int[] a = new int[n + 1];
a[0] = 0;
for (int i = 1; i <= n; i++) {
a[i] = a[i - 1] + arr[i - 1];
}
// Initialize the ans with large value
int ans = Int16.MaxValue;
// There are total four parts means 3 cuts.
// Here i, j, k represent those 3 cuts
for (int i = 1, j = 2, k = 3; j < n; j++) {
while (i + 1 < j
&& Math.Abs(a[j] - 2 * a[i])
> Math.Abs(a[j] - 2 * a[i + 1])) {
i++;
}
while (k + 1 < n
&& Math.Abs(a[n] + a[j] - 2 * a[k])
> Math.Abs(a[n] + a[j]
- 2 * a[k + 1])) {
k++;
}
ans = Math.Min(
ans,
Math.Max(a[i],
Math.Max(a[j] - a[i],
Math.Max(a[k] - a[j],
a[n] - a[k])))
- Math.Min(
a[i],
Math.Min(a[j] - a[i],
Math.Min(a[k] - a[j],
a[n] - a[k]))));
}
return ans;
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 3, 2, 4, 1, 2 };
int N = arr.Length;
// Function call
Console.WriteLine(minCost(arr, N));
}
}
// This code is contributed by Pushpesh Raj
Javascript
<script>
// JavaScript code to implement the approach
// Function to find the minimum difference
// between maximum and minimum subarray sum
// after dividing the array into 4 subarrays
const minSum = (v, n) => {
let a = new Array(n + 1).fill(0);
// Precompute the prefix sum
a[0] = 0;
for (let i = 1; i <= n; i++) {
a[i] = a[i - 1] + v[i - 1];
}
// Initialize the ans with large value
let ans = 1e18;
// There are total four parts means 3 cuts.
// Here i, j, k represent those 3 cuts
for (let i = 1, j = 2, k = 3; j < n; j++) {
while (i + 1 < j
&& Math.abs(a[j] - 2 * a[i])
> Math.abs(a[j]
- 2 * a[i + 1])) {
i++;
}
while (k + 1 < n
&& Math.abs(a[n] + a[j] - 2 * a[k])
> Math.abs(a[n] + a[j]
- 2 * a[k + 1])) {
k++;
}
ans = Math.min(ans,
Math.max(...[a[i], a[j] - a[i],
a[k] - a[j],
a[n] - a[k]])
- Math.min(...[a[i], a[j] - a[i],
a[k] - a[j],
a[n] - a[k]]));
}
return ans;
}
// Driver Code
let arr = [3, 2, 4, 1, 2];
let N = arr.length;
// Function call
document.write(minSum(arr, N));
// This code is contributed by rakeshsahni
</script>
Producción
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)