Dada una array de enteros, encuentre dos subarreglos contiguos que no se superpongan de modo que la diferencia absoluta entre la suma de dos subarreglos sea máxima.
Ejemplo:
Input: [-2, -3, 4, -1, -2, 1, 5, -3] Output: 12 Two subarrays are [-2, -3] and [4, -1, -2, 1, 5] Input: [2, -1, -2, 1, -4, 2, 8] Output: 16 Two subarrays are [-1, -2, 1, -4] and [2, 8]
La complejidad de tiempo esperada es O(n).
La idea es que para cada índice i en el arreglo dado arr[0…n-1], calcule los subarreglos de suma máxima y mínima que se encuentran en los subarreglos arr[0…i] y arr[i+1…n-1]. Mantenemos cuatro arreglos que almacenan las sumas máxima y mínima en los subarreglos arr[0…i] y arr[i+1…n-1] para cada índice i en el arreglo.
leftMax[] : An element leftMax[i] of this
array stores the maximum value
in subarray arr[0..i]
leftMin[] : An element leftMin[i] of this
array stores the minimum value
in subarray arr[0..i]
rightMax[] : An element rightMax[i] of this
array stores the maximum value
in subarray arr[i+1..n-1]
rightMin[] : An element rightMin[i] of this
array stores the minimum value
in subarray arr[i+1..n-1]
Podemos construir más de cuatro arreglos en tiempo O(n) usando el Algoritmo de Kadane .
- Para calcular el subarreglo de suma máxima que se encuentra en arr[0…i], ejecutamos el algoritmo Kadane de 0 a n-1 y para encontrar el subarreglo de suma máxima que se encuentra en arr[i+1 … n-1], ejecutamos Kadane Algoritmo de n-1 a 0.
- El algoritmo de Kadane también se puede modificar para encontrar la suma absoluta mínima de un subarreglo. La idea es cambiar el signo de cada elemento en la array y ejecutar el Algoritmo de Kadane para encontrar la suma máxima del subarreglo que se encuentra en arr[0…i] y arr[i+1…n-1]. Ahora invierta el signo de la suma máxima de subarreglo encontrada. Esa será nuestra suma mínima de subarreglo. Esta idea está tomada de aquí .
Ahora, desde las cuatro arrays anteriores, podemos encontrar fácilmente la máxima diferencia absoluta entre la suma de dos sub-arrays contiguas. Para cada índice i, tome el máximo de
- abs(suma máxima de subarreglo que se encuentra en arr[0…i] – suma mínima de subarreglo que se encuentra en arr[i+1…n-1])
- abs(suma mínima de subarreglo que se encuentra en arr[0…i] – suma máxima de subarreglo que se encuentra en arr[i+1…n-1])
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to find two non-overlapping contiguous
// sub-arrays such that the absolute difference
// between the sum of two sub-array is maximum.
#include <bits/stdc++.h>
using namespace std;
// Find maximum subarray sum for subarray [0..i]
// using standard Kadane's algorithm. This version of
// Kadane's Algorithm will work if all numbers are
// negative.
int maxLeftSubArraySum(int a[], int size, int sum[])
{
int max_so_far = a[0];
int curr_max = a[0];
sum[0] = max_so_far;
for (int i = 1; i < size; i++)
{
curr_max = max(a[i], curr_max + a[i]);
max_so_far = max(max_so_far, curr_max);
sum[i] = max_so_far;
}
return max_so_far;
}
// Find maximum subarray sum for subarray [i..n]
// using Kadane's algorithm. This version of Kadane's
// Algorithm will work if all numbers are negative
int maxRightSubArraySum(int a[], int n, int sum[])
{
int max_so_far = a[n];
int curr_max = a[n];
sum[n] = max_so_far;
for (int i = n-1; i >= 0; i--)
{
curr_max = max(a[i], curr_max + a[i]);
max_so_far = max(max_so_far, curr_max);
sum[i] = max_so_far;
}
return max_so_far;
}
// The function finds two non-overlapping contiguous
// sub-arrays such that the absolute difference
// between the sum of two sub-array is maximum.
int findMaxAbsDiff(int arr[], int n)
{
// create and build an array that stores
// maximum sums of subarrays that lie in
// arr[0...i]
int leftMax[n];
maxLeftSubArraySum(arr, n, leftMax);
// create and build an array that stores
// maximum sums of subarrays that lie in
// arr[i+1...n-1]
int rightMax[n];
maxRightSubArraySum(arr, n-1, rightMax);
// Invert array (change sign) to find minumum
// sum subarrays.
int invertArr[n];
for (int i = 0; i < n; i++)
invertArr[i] = -arr[i];
// create and build an array that stores
// minimum sums of subarrays that lie in
// arr[0...i]
int leftMin[n];
maxLeftSubArraySum(invertArr, n, leftMin);
for (int i = 0; i < n; i++)
leftMin[i] = -leftMin[i];
// create and build an array that stores
// minimum sums of subarrays that lie in
// arr[i+1...n-1]
int rightMin[n];
maxRightSubArraySum(invertArr, n - 1, rightMin);
for (int i = 0; i < n; i++)
rightMin[i] = -rightMin[i];
int result = INT_MIN;
for (int i = 0; i < n - 1; i++)
{
/* For each index i, take maximum of
1. abs(max sum subarray that lies in arr[0...i] -
min sum subarray that lies in arr[i+1...n-1])
2. abs(min sum subarray that lies in arr[0...i] -
max sum subarray that lies in arr[i+1...n-1]) */
int absValue = max(abs(leftMax[i] - rightMin[i + 1]),
abs(leftMin[i] - rightMax[i + 1]));
if (absValue > result)
result = absValue;
}
return result;
}
// Driver program
int main()
{
int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};
int n = sizeof(a) / sizeof(a[0]);
cout << findMaxAbsDiff(a, n);
return 0;
}
Java
// Java program to find two non-overlapping
// contiguous sub-arrays such that the
// absolute difference
import java.util.*;
class GFG {
// Find maximum subarray sum for subarray
// [0..i] using standard Kadane's algorithm.
// This version of Kadane's Algorithm will
// work if all numbers are negative.
static int maxLeftSubArraySum(int a[], int size,
int sum[])
{
int max_so_far = a[0];
int curr_max = a[0];
sum[0] = max_so_far;
for (int i = 1; i < size; i++) {
curr_max = Math.max(a[i], curr_max + a[i]);
max_so_far = Math.max(max_so_far, curr_max);
sum[i] = max_so_far;
}
return max_so_far;
}
// Find maximum subarray sum for subarray [i..n]
// using Kadane's algorithm. This version of Kadane's
// Algorithm will work if all numbers are negative
static int maxRightSubArraySum(int a[], int n, int sum[])
{
int max_so_far = a[n];
int curr_max = a[n];
sum[n] = max_so_far;
for (int i = n - 1; i >= 0; i--) {
curr_max = Math.max(a[i], curr_max + a[i]);
max_so_far = Math.max(max_so_far, curr_max);
sum[i] = max_so_far;
}
return max_so_far;
}
// The function finds two non-overlapping contiguous
// sub-arrays such that the absolute difference
// between the sum of two sub-array is maximum.
static int findMaxAbsDiff(int arr[], int n)
{
// create and build an array that stores
// maximum sums of subarrays that lie in
// arr[0...i]
int leftMax[] = new int[n];
maxLeftSubArraySum(arr, n, leftMax);
// create and build an array that stores
// maximum sums of subarrays that lie in
// arr[i+1...n-1]
int rightMax[] = new int[n];
maxRightSubArraySum(arr, n - 1, rightMax);
// Invert array (change sign) to find minumum
// sum subarrays.
int invertArr[] = new int[n];
for (int i = 0; i < n; i++)
invertArr[i] = -arr[i];
// create and build an array that stores
// minimum sums of subarrays that lie in
// arr[0...i]
int leftMin[] = new int[n];
maxLeftSubArraySum(invertArr, n, leftMin);
for (int i = 0; i < n; i++)
leftMin[i] = -leftMin[i];
// create and build an array that stores
// minimum sums of subarrays that lie in
// arr[i+1...n-1]
int rightMin[] = new int[n];
maxRightSubArraySum(invertArr, n - 1, rightMin);
for (int i = 0; i < n; i++)
rightMin[i] = -rightMin[i];
int result = -2147483648;
for (int i = 0; i < n - 1; i++) {
/* For each index i, take maximum of
1. abs(max sum subarray that lies in arr[0...i] -
min sum subarray that lies in arr[i+1...n-1])
2. abs(min sum subarray that lies in arr[0...i] -
max sum subarray that lies in arr[i+1...n-1]) */
int absValue = Math.max(Math.abs(leftMax[i] - rightMin[i + 1]),
Math.abs(leftMin[i] - rightMax[i + 1]));
if (absValue > result)
result = absValue;
}
return result;
}
// driver code
public static void main(String[] args)
{
int a[] = { -2, -3, 4, -1, -2, 1, 5, -3 };
int n = a.length;
System.out.print(findMaxAbsDiff(a, n));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python3 program to find two non- # overlapping contiguous sub-arrays # such that the absolute difference # between the sum of two sub-array is maximum. # Find maximum subarray sum for # subarray [0..i] using standard # Kadane's algorithm. This version # of Kadane's Algorithm will work if # all numbers are negative. def maxLeftSubArraySum(a, size, sum): max_so_far = a[0] curr_max = a[0] sum[0] = max_so_far for i in range(1, size): curr_max = max(a[i], curr_max + a[i]) max_so_far = max(max_so_far, curr_max) sum[i] = max_so_far return max_so_far # Find maximum subarray sum for # subarray [i..n] using Kadane's # algorithm. This version of Kadane's # Algorithm will work if all numbers are negative def maxRightSubArraySum(a, n, sum): max_so_far = a[n] curr_max = a[n] sum[n] = max_so_far for i in range(n - 1, -1, -1): curr_max = max(a[i], curr_max + a[i]) max_so_far = max(max_so_far, curr_max) sum[i] = max_so_far return max_so_far # The function finds two non-overlapping # contiguous sub-arrays such that the # absolute difference between the sum # of two sub-array is maximum. def findMaxAbsDiff(arr, n): # create and build an array that # stores maximum sums of subarrays # that lie in arr[0...i] leftMax = [0 for i in range(n)] maxLeftSubArraySum(arr, n, leftMax) # create and build an array that stores # maximum sums of subarrays that lie in # arr[i+1...n-1] rightMax = [0 for i in range(n)] maxRightSubArraySum(arr, n-1, rightMax) # Invert array (change sign) to # find minumum sum subarrays. invertArr = [0 for i in range(n)] for i in range(n): invertArr[i] = -arr[i] # create and build an array that stores # minimum sums of subarrays that lie in # arr[0...i] leftMin = [0 for i in range(n)] maxLeftSubArraySum(invertArr, n, leftMin) for i in range(n): leftMin[i] = -leftMin[i] # create and build an array that stores # minimum sums of subarrays that lie in # arr[i+1...n-1] rightMin = [0 for i in range(n)] maxRightSubArraySum(invertArr, n - 1, rightMin) for i in range(n): rightMin[i] = -rightMin[i] result = -2147483648 for i in range(n - 1): ''' For each index i, take maximum of 1. abs(max sum subarray that lies in arr[0...i] - min sum subarray that lies in arr[i+1...n-1]) 2. abs(min sum subarray that lies in arr[0...i] - max sum subarray that lies in arr[i+1...n-1]) ''' absValue = max(abs(leftMax[i] - rightMin[i + 1]), abs(leftMin[i] - rightMax[i + 1])) if (absValue > result): result = absValue return result # Driver Code a = [-2, -3, 4, -1, -2, 1, 5, -3] n = len(a) print(findMaxAbsDiff(a, n)) # This code is contributed by Anant Agarwal.
C#
// C# program to find two non-overlapping
// contiguous sub-arrays such that the
// absolute difference
using System;
class GFG {
// Find maximum subarray sum for subarray
// [0..i] using standard Kadane's algorithm.
// This version of Kadane's Algorithm will
// work if all numbers are negative.
static int maxLeftSubArraySum(int []a, int size,
int []sum)
{
int max_so_far = a[0];
int curr_max = a[0];
sum[0] = max_so_far;
for (int i = 1; i < size; i++)
{
curr_max = Math.Max(a[i], curr_max + a[i]);
max_so_far = Math.Max(max_so_far, curr_max);
sum[i] = max_so_far;
}
return max_so_far;
}
// Find maximum subarray sum for subarray
// [i..n] using Kadane's algorithm.
// This version of Kadane's Algorithm will
// work if all numbers are negative
static int maxRightSubArraySum(int []a, int n,
int []sum)
{
int max_so_far = a[n];
int curr_max = a[n];
sum[n] = max_so_far;
for (int i = n-1; i >= 0; i--)
{
curr_max = Math.Max(a[i], curr_max + a[i]);
max_so_far = Math.Max(max_so_far, curr_max);
sum[i] = max_so_far;
}
return max_so_far;
}
// The function finds two non-overlapping
// contiguous sub-arrays such that the
// absolute difference between the sum
// of two sub-array is maximum.
static int findMaxAbsDiff(int []arr, int n)
{
// create and build an array that stores
// maximum sums of subarrays that lie in
// arr[0...i]
int []leftMax=new int[n];
maxLeftSubArraySum(arr, n, leftMax);
// create and build an array that stores
// maximum sums of subarrays that lie in
// arr[i+1...n-1]
int []rightMax=new int[n];
maxRightSubArraySum(arr, n-1, rightMax);
// Invert array (change sign) to find minumum
// sum subarrays.
int []invertArr=new int[n];
for (int i = 0; i < n; i++)
invertArr[i] = -arr[i];
// create and build an array that stores
// minimum sums of subarrays that lie in
// arr[0...i]
int []leftMin=new int[n];
maxLeftSubArraySum(invertArr, n, leftMin);
for (int i = 0; i < n; i++)
leftMin[i] = -leftMin[i];
// create and build an array that stores
// minimum sums of subarrays that lie in
// arr[i+1...n-1]
int []rightMin=new int[n];
maxRightSubArraySum(invertArr, n - 1, rightMin);
for (int i = 0; i < n; i++)
rightMin[i] = -rightMin[i];
int result = -2147483648;
for (int i = 0; i < n - 1; i++)
{
/* For each index i, take maximum of
1. abs(max sum subarray that lies in arr[0...i] -
min sum subarray that lies in arr[i+1...n-1])
2. abs(min sum subarray that lies in arr[0...i] -
max sum subarray that lies in arr[i+1...n-1]) */
int absValue = Math.Max(Math.Abs(leftMax[i] - rightMin[i + 1]),
Math.Abs(leftMin[i] - rightMax[i + 1]));
if (absValue > result)
result = absValue;
}
return result;
}
//driver code
public static void Main()
{
int []a= {-2, -3, 4, -1, -2, 1, 5, -3};
int n = a.Length;
Console.Write(findMaxAbsDiff(a, n));
}
}
//This code is contributed by Anant Agarwal.
PHP
<?php
// PHP program to find two non-overlapping
// contiguous sub-arrays such that the
// absolute difference between the sum of
// two sub-array is maximum.
// Find maximum subarray sum for subarray
// [0..i] using standard Kadane's algorithm.
// This version of Kadane's Algorithm will
// work if all numbers are negative
function maxLeftSubArraySum(&$a, $size, &$sum)
{
$max_so_far = $a[0];
$curr_max = $a[0];
$sum[0] = $max_so_far;
for ($i = 1; $i < $size; $i++)
{
$curr_max = max($a[$i],
$curr_max + $a[$i]);
$max_so_far = max($max_so_far,
$curr_max);
$sum[$i] = $max_so_far;
}
return $max_so_far;
}
// Find maximum subarray sum for subarray
// [i..n] using Kadane's algorithm. This
// version of Kadane's Algorithm will work
// if all numbers are negative
function maxRightSubArraySum(&$a, $n, &$sum)
{
$max_so_far = $a[$n];
$curr_max = $a[$n];
$sum[$n] = $max_so_far;
for ($i = $n - 1; $i >= 0; $i--)
{
$curr_max = max($a[$i],
$curr_max + $a[$i]);
$max_so_far = max($max_so_far,
$curr_max);
$sum[$i] = $max_so_far;
}
return $max_so_far;
}
// The function finds two non-overlapping
// contiguous sub-arrays such that the
// absolute difference between the sum of
// two sub-array is maximum.
function findMaxAbsDiff(&$arr, $n)
{
// create and build an array that stores
// maximum sums of subarrays that lie in
// arr[0...i]
$leftMax = array_fill(0, $n, NULL);
maxLeftSubArraySum($arr, $n, $leftMax);
// create and build an array that stores
// maximum sums of subarrays that lie in
// arr[i+1...n-1]
$rightMax = array_fill(0, $n, NULL);
maxRightSubArraySum($arr, $n - 1, $rightMax);
// Invert array (change sign) to
// find minumum sum subarrays
$invertArr = array_fill(0, $n, NULL);
for ($i = 0; $i < $n; $i++)
$invertArr[$i] = -$arr[$i];
// create and build an array that stores
// minimum sums of subarrays that lie in
// arr[0...i]
$leftMin = array_fill(0, $n, NULL);
maxLeftSubArraySum($invertArr, $n,
$leftMin);
for ($i = 0; $i < $n; $i++)
$leftMin[$i] = -$leftMin[$i];
// create and build an array that stores
// minimum sums of subarrays that lie in
// arr[i+1...n-1]
$rightMin = array_fill(0, $n, NULL);
maxRightSubArraySum($invertArr,
$n - 1, $rightMin);
for ($i = 0; $i < $n; $i++)
$rightMin[$i] = -$rightMin[$i];
$result = PHP_INT_MIN;
for ($i = 0; $i <$n - 1; $i++)
{
/* For each index i, take maximum of
1. abs(max sum subarray that lies
in arr[0...i] - min sum subarray
that lies in arr[i+1...n-1])
2. abs(min sum subarray that lies
in arr[0...i] - max sum subarray
that lies in arr[i+1...n-1]) */
$absValue = max(abs($leftMax[$i] -
$rightMin[$i + 1]),
abs($leftMin[$i] -
$rightMax[$i + 1]));
if ($absValue > $result)
$result = $absValue;
}
return $result;
}
// Driver Code
$a = array(-2, -3, 4, -1, -2, 1, 5, -3);
$n = sizeof($a);
echo findMaxAbsDiff($a, $n);
// This code is contributed
// by ChitraNayal
?>
Producción
12
La complejidad del tiempo es O(n) donde n es el número de elementos en la array de entrada. El espacio auxiliar requerido es O(n).
Este artículo es una contribución de Aditya Goel . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA