Dada una array de enteros arr[] , la tarea es dividir la array dada en dos subarreglos de modo que la diferencia entre su suma sea mínima.
Ejemplos:
Entrada: arr[] = {7, 9, 5, 10}
Salida: 1
Explicación: La diferencia entre la suma de los subarreglos {7, 9} y {5, 10} es igual a [16 – 15] = 1, que es lo mínimo posible.Entrada: arr[] = {6, 6, 6}
Salida : 6
Enfoque ingenuo: la idea es utilizar la técnica de array Prefix and Suffix Sum . Genere la array de suma de prefijos y la array de suma de sufijos de la array dada. Ahora, itere sobre la array e imprima la diferencia mínima entre prefix_sum[i] y suffix_sum[i+1] , para cualquier índice i ( 0 <= i <= N – 1) de la array.
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
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 return minimum difference
// between two subarray sums
int minDiffSubArray(int arr[], int n)
{
// To store prefix sums
int prefix_sum[n];
// Generate prefix sum array
prefix_sum[0] = arr[0];
for(int i = 1; i < n; i++)
prefix_sum[i] = prefix_sum[i - 1] +
arr[i];
// To store suffix sums
int suffix_sum[n];
// Generate suffix sum array
suffix_sum[n - 1] = arr[n - 1];
for(int i = n - 2; i >= 0; i--)
suffix_sum[i] = suffix_sum[i + 1] +
arr[i];
// Stores the minimum difference
int minDiff = INT_MAX;
// Traverse the given array
for(int i = 0; i < n - 1; i++)
{
// Calculate the difference
int diff = abs(prefix_sum[i] -
suffix_sum[i + 1]);
// Update minDiff
if (diff < minDiff)
minDiff = diff;
}
// Return minDiff
return minDiff;
}
// Driver Code
int main()
{
// Given array
int arr[] = { 7, 9, 5, 10 };
// Length of the array
int n = sizeof(arr) / sizeof(arr[0]);
cout << minDiffSubArray(arr, n);
}
// This code is contributed by code_hunt
Java
// Java Program for above approach
import java.util.*;
import java.lang.*;
class GFG {
// Function to return minimum difference
// between two subarray sums
static int minDiffSubArray(int arr[], int n)
{
// To store prefix sums
int[] prefix_sum = new int[n];
// Generate prefix sum array
prefix_sum[0] = arr[0];
for (int i = 1; i < n; i++)
prefix_sum[i]
= prefix_sum[i - 1] + arr[i];
// To store suffix sums
int[] suffix_sum = new int[n];
// Generate suffix sum array
suffix_sum[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--)
suffix_sum[i]
= suffix_sum[i + 1] + arr[i];
// Stores the minimum difference
int minDiff = Integer.MAX_VALUE;
// Traverse the given array
for (int i = 0; i < n - 1; i++) {
// Calculate the difference
int diff
= Math.abs(prefix_sum[i]
- suffix_sum[i + 1]);
// Update minDiff
if (diff < minDiff)
minDiff = diff;
}
// Return minDiff
return minDiff;
}
// Driver Code
public static void main(String[] args)
{
// Given array
int[] arr = { 7, 9, 5, 10 };
// Length of the array
int n = arr.length;
System.out.println(
minDiffSubArray(arr, n));
}
}
Python3
# Python3 program for the above approach import sys # Function to return minimum difference # between two subarray sums def minDiffSubArray(arr, n): # To store prefix sums prefix_sum = [0] * n # Generate prefix sum array prefix_sum[0] = arr[0] for i in range(1, n): prefix_sum[i] = (prefix_sum[i - 1] + arr[i]) # To store suffix sums suffix_sum = [0] * n # Generate suffix sum array suffix_sum[n - 1] = arr[n - 1] for i in range(n - 2, -1, -1): suffix_sum[i] = (suffix_sum[i + 1] + arr[i]) # Stores the minimum difference minDiff = sys.maxsize # Traverse the given array for i in range(n - 1): # Calculate the difference diff = abs(prefix_sum[i] - suffix_sum[i + 1]) # Update minDiff if (diff < minDiff): minDiff = diff # Return minDiff return minDiff # Driver Code if __name__ == '__main__': # Given array arr = [ 7, 9, 5, 10 ] # Length of the array n = len(arr) print(minDiffSubArray(arr, n)) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// Function to return minimum difference
// between two subarray sums
static int minDiffSubArray(int []arr,
int n)
{
// To store prefix sums
int[] prefix_sum = new int[n];
// Generate prefix sum array
prefix_sum[0] = arr[0];
for(int i = 1; i < n; i++)
prefix_sum[i] = prefix_sum[i - 1] +
arr[i];
// To store suffix sums
int[] suffix_sum = new int[n];
// Generate suffix sum array
suffix_sum[n - 1] = arr[n - 1];
for(int i = n - 2; i >= 0; i--)
suffix_sum[i] = suffix_sum[i + 1] +
arr[i];
// Stores the minimum difference
int minDiff = int.MaxValue;
// Traverse the given array
for(int i = 0; i < n - 1; i++)
{
// Calculate the difference
int diff = Math.Abs(prefix_sum[i] -
suffix_sum[i + 1]);
// Update minDiff
if (diff < minDiff)
minDiff = diff;
}
// Return minDiff
return minDiff;
}
// Driver Code
public static void Main(String[] args)
{
// Given array
int[] arr = {7, 9, 5, 10};
// Length of the array
int n = arr.Length;
Console.WriteLine(minDiffSubArray(arr, n));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program for the above approach
// Function to return minimum difference
// between two subarray sums
function minDiffSubArray(arr, n)
{
// To store prefix sums
let prefix_sum = new Array(n);
// Generate prefix sum array
prefix_sum[0] = arr[0];
for(let i = 1; i < n; i++)
prefix_sum[i] = prefix_sum[i - 1] + arr[i];
// To store suffix sums
let suffix_sum = new Array(n);
// Generate suffix sum array
suffix_sum[n - 1] = arr[n - 1];
for(let i = n - 2; i >= 0; i--)
suffix_sum[i] = suffix_sum[i + 1] + arr[i];
// Stores the minimum difference
let minDiff = Number.MAX_VALUE;
// Traverse the given array
for(let i = 0; i < n - 1; i++)
{
// Calculate the difference
let diff = Math.abs(prefix_sum[i] - suffix_sum[i + 1]);
// Update minDiff
if (diff < minDiff)
minDiff = diff;
}
// Return minDiff
return minDiff;
}
// Given array
let arr = [7, 9, 5, 10];
// Length of the array
let n = arr.length;
document.write(minDiffSubArray(arr, n));
// This code is contributed by vaibhavrabadiya117.
</script>
Producción:
1
Enfoque eficiente: para optimizar el enfoque anterior, la idea es calcular la suma total de los elementos de la array. Ahora, itere sobre la array y calcule la suma del prefijo de la array y encuentre la diferencia mínima entre la suma del prefijo y la diferencia entre la suma total y la suma del prefijo para cualquier índice de la array, es decir,
Diferencia máxima entre la suma de los subarreglos = ( prefix_sum – (total_sum – prefix_sum) )
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return minimum difference
// between sum of two subarrays
int minDiffSubArray(int arr[], int n)
{
// To store total sum of array
int total_sum = 0;
// Calculate the total sum
// of the array
for(int i = 0; i < n; i++)
total_sum += arr[i];
// Stores the prefix sum
int prefix_sum = 0;
// Stores the minimum difference
int minDiff = INT_MAX;
// Traverse the given array
for(int i = 0; i < n - 1; i++)
{
prefix_sum += arr[i];
// To store minimum difference
int diff = abs((total_sum -
prefix_sum) -
prefix_sum);
// Update minDiff
if (diff < minDiff)
minDiff = diff;
}
// Return minDiff
return minDiff;
}
// Driver code
int main()
{
// Given array
int arr[] = { 7, 9, 5, 10 };
// Length of the array
int n = sizeof(arr) / sizeof(arr[0]);
cout << minDiffSubArray(arr, n) << endl;
return 0;
}
// This code is contributed by divyeshrabadiya07
Java
// Java Program for above approach
import java.util.*;
import java.lang.*;
class GFG {
// Function to return minimum difference
// between sum of two subarrays
static int minDiffSubArray(int arr[], int n)
{
// To store total sum of array
int total_sum = 0;
// Calculate the total sum
// of the array
for (int i = 0; i < n; i++)
total_sum += arr[i];
// Stores the prefix sum
int prefix_sum = 0;
// Stores the minimum difference
int minDiff = Integer.MAX_VALUE;
// Traverse the given array
for (int i = 0; i < n - 1; i++) {
prefix_sum += arr[i];
// To store minimum difference
int diff
= Math.abs((total_sum
- prefix_sum)
- prefix_sum);
// Update minDiff
if (diff < minDiff)
minDiff = diff;
}
// Return minDiff
return minDiff;
}
// Driver Code
public static void main(String[] args)
{
// Given array
int[] arr = { 7, 9, 5, 10 };
// Length of the array
int n = arr.length;
System.out.println(
minDiffSubArray(arr, n));
}
}
Python3
# Python3 program for the above approach import sys # Function to return minimum difference # between sum of two subarrays def minDiffSubArray(arr, n): # To store total sum of array total_sum = 0 # Calculate the total sum # of the array for i in range(n): total_sum += arr[i] # Stores the prefix sum prefix_sum = 0 # Stores the minimum difference minDiff = sys.maxsize # Traverse the given array for i in range(n - 1): prefix_sum += arr[i] # To store minimum difference diff = abs((total_sum - prefix_sum) - prefix_sum) # Update minDiff if (diff < minDiff): minDiff = diff # Return minDiff return minDiff # Driver code # Given array arr = [ 7, 9, 5, 10 ] # Length of the array n = len(arr) print(minDiffSubArray(arr, n)) # This code is contributed by code_hunt
C#
// C# Program for above approach
using System;
class GFG{
// Function to return minimum difference
// between sum of two subarrays
static int minDiffSubArray(int []arr,
int n)
{
// To store total sum of array
int total_sum = 0;
// Calculate the total sum
// of the array
for (int i = 0; i < n; i++)
total_sum += arr[i];
// Stores the prefix sum
int prefix_sum = 0;
// Stores the minimum difference
int minDiff = int.MaxValue;
// Traverse the given array
for (int i = 0; i < n - 1; i++)
{
prefix_sum += arr[i];
// To store minimum difference
int diff = Math.Abs((total_sum -
prefix_sum) -
prefix_sum);
// Update minDiff
if (diff < minDiff)
minDiff = diff;
}
// Return minDiff
return minDiff;
}
// Driver Code
public static void Main(String[] args)
{
// Given array
int[] arr = {7, 9, 5, 10};
// Length of the array
int n = arr.Length;
Console.WriteLine(
minDiffSubArray(arr, n));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program for above approach
// Function to return minimum difference
// between sum of two subarrays
function minDiffSubArray(arr, n)
{
// To store total sum of array
var total_sum = 0;
// Calculate the total sum
// of the array
for(var i = 0; i < n; i++)
total_sum += arr[i];
// Stores the prefix sum
var prefix_sum = 0;
// Stores the minimum difference
var minDiff = 1000000000;
// Traverse the given array
for(var i = 0; i < n - 1; i++)
{
prefix_sum += arr[i];
// To store minimum difference
var diff = Math.abs((total_sum -
prefix_sum) -
prefix_sum);
// Update minDiff
if (diff < minDiff)
minDiff = diff;
}
// Return minDiff
return minDiff;
}
// Driver code
// Given array
var arr = [7, 9, 5, 10];
// Length of the array
var n = arr.length;
document.write( minDiffSubArray(arr, n));
// This code is contributed by importantly.
</script>
Producción:
1
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array