Minimice la suma de un Array intercambiando un Subarray con otro Array

Dados dos arreglos A [] y B [] cada uno de tamaño N , la tarea es minimizar la suma de un arreglo intercambiando un subarreglo.

Ejemplos : 

Entrada : A[] = {10, 30, 10, 60, 20}, B[] = {40, 10, 40, 30, 10}
Salida : 90
Explicación : Intercambie el subarreglo {30, 10} con {60, 20}.
La suma del arreglo A[] = 10+30+10+30+10 = 90.
La suma del arreglo B[] = 40+10+40+60+20 = 170.
La suma mínima = 90. 
Es el mínimo suma posible que puede lograr una array.

Entrada : A[] = {10, 20, 30}, B[] = {1, 2, 3}
Salida : 6

Enfoque : el problema se puede resolver con base en la siguiente idea:

Para minimizar la suma de una array, debemos intercambiar una subarreglo donde la diferencia entre la suma del subarreglo sea máxima, es decir, para la array A[] el valor de ( subarreglo de A[] – subarreglo de B[] ) es máximo y el mismo para la array B[] . 
El mínimo entre estos dos valores será la respuesta.

Para implementar esto, podemos crear dos arrays de diferencia y calcular la suma de subarreglo más grande de esas arrays de diferencia y restarlas de la suma de la array.

Siga los pasos mencionados a continuación para implementar la idea anterior:

• Cree dos arrays de diferencia (digamos t[] y s[] ) para almacenar los valores de (A[i]-B[i]) y (B[i]-A[i]) respectivamente.
• Calcular la suma de las arrays.
• Ahora encuentre las sumas máximas de subarreglo de t[] y s[] usando el algoritmo de Kadane .
• Reste estos valores de la suma de la array respectiva y el mínimo entre ellos es la respuesta requerida.

A continuación se muestra la implementación del enfoque anterior.

// C++ code to implement the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return Max Sum Subarray
int maxSubArraySum(vector<int> a)
{
    int max_so_far = INT_MIN, max_ending_here = 0;
    int size = a.size();
 
    // Loop to find the maximum subarray sum
    for (int i = 0; i < size; i++) {
        max_ending_here = max_ending_here + a[i];
        if (max_so_far < max_ending_here) {
            max_so_far = max_ending_here;
        }
        if (max_ending_here < 0) {
            max_ending_here = 0;
        }
    }
 
    // Return the maximmum subarray sum
    return max_so_far;
}
 
// Function to find Minimum Sum after replacement
 
int findMaxSum(vector<int>& nums1,
               vector<int>& nums2)
{
    int n = nums1.size();
    vector<int> s(n), t(n);
 
    // Calculating Sum of nums1 and nums2
    int S1 = 0, S2 = 0;
    for (int i = 0; i < n; i++) {
        S1 += nums1[i];
        S2 += nums2[i];
    }
 
    // Creating difference arrays
    for (int i = 0; i < n; i++) {
        t[i] = nums1[i] - nums2[i];
        s[i] = nums2[i] - nums1[i];
    }
 
    // Return Min Sum
    return min(S2 - maxSubArraySum(s),
               S1 - maxSubArraySum(t));
}
 
// Driver Code
int main()
{
    vector<int> A = { 10, 30, 10, 60, 20 };
    vector<int> B = { 40, 10, 40, 30, 10 };
 
    // Function Call
    cout << findMaxSum(A, B);
    return 0;
}

// Java code to implement the above approach
import java.io.*;
 
class GFG {
    // Function to return Max Sum Subarray
    public static int maxSubArraySum(int a[])
    {
        int max_so_far = Integer.MIN_VALUE, max_ending_here
                                            = 0;
        int size = a.length;
 
        // Loop to find the maximum subarray sum
        for (int i = 0; i < size; i++) {
            max_ending_here = max_ending_here + a[i];
            if (max_so_far < max_ending_here) {
                max_so_far = max_ending_here;
            }
            if (max_ending_here < 0) {
                max_ending_here = 0;
            }
        }
 
        // Return the maximmum subarray sum
        return max_so_far;
    }
 
    // Function to find Minimum Sum after replacement
 
    public static int findMaxSum(int nums1[], int nums2[])
    {
        int n = nums1.length;
        int s[] = new int[n];
        int t[] = new int[n];
 
        // Calculating Sum of nums1 and nums2
        int S1 = 0, S2 = 0;
        for (int i = 0; i < n; i++) {
            S1 += nums1[i];
            S2 += nums2[i];
        }
 
        // Creating difference arrays
        for (int i = 0; i < n; i++) {
            t[i] = nums1[i] - nums2[i];
            s[i] = nums2[i] - nums1[i];
        }
 
        // Return Min Sum
        return Math.min(S2 - maxSubArraySum(s),
                        S1 - maxSubArraySum(t));
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int A[] = { 10, 30, 10, 60, 20 };
        int B[] = { 40, 10, 40, 30, 10 };
 
        // Function Call
        System.out.print(findMaxSum(A, B));
    }
}
 
// This code is contributed by Rohit Pradhan

using System;
 
public class GFG {
 
    // Function to return Max Sum Subarray
    public static int maxSubArraySum(int[] a)
    {
        int max_so_far = Int32.MinValue, max_ending_here
                                         = 0;
        int size = a.Length;
 
        // Loop to find the maximum subarray sum
        for (int i = 0; i < size; i++) {
            max_ending_here = max_ending_here + a[i];
            if (max_so_far < max_ending_here) {
                max_so_far = max_ending_here;
            }
            if (max_ending_here < 0) {
                max_ending_here = 0;
            }
        }
 
        // Return the maximmum subarray sum
        return max_so_far;
    }
 
    // Function to find Minimum Sum after replacement
    public static int findMaxSum(int[] nums1, int[] nums2)
    {
        int n = nums1.Length;
        int[] s = new int[n];
        int[] t = new int[n];
 
        // Calculating sum of nums1 and nums2
        int S1 = 0, S2 = 0;
        for (int i = 0; i < n; i++) {
            S1 += nums1[i];
            S2 += nums2[i];
        }
 
        // Creating difference arrays
        for (int i = 0; i < n; i++) {
            t[i] = nums1[i] - nums2[i];
            s[i] = nums2[i] - nums1[i];
        }
 
        // return Min Sum
        return Math.Min(S2 - maxSubArraySum(s),
                        S1 - maxSubArraySum(t));
    }
 
    static public void Main()
    {
 
        // Code
        int[] A = { 10, 30, 10, 60, 20 };
        int[] B = { 40, 10, 40, 30, 10 };
 
        // Function call
        Console.Write(findMaxSum(A, B));
    }
}
 
// This code is contributed by lokesh (lokeshmvs21).

<script>
    // JavaScript code to implement the above approach
    const INT_MIN = -2147483648;
     
    // Function to return Max Sum Subarray
    const maxSubArraySum = (a) => {
        let max_so_far = INT_MIN, max_ending_here = 0;
        let size = a.length;
 
        // Loop to find the maximum subarray sum
        for (let i = 0; i < size; i++)
        {
            max_ending_here = max_ending_here + a[i];
            if (max_so_far < max_ending_here) {
                max_so_far = max_ending_here;
            }
            if (max_ending_here < 0) {
                max_ending_here = 0;
            }
        }
 
        // Return the maximmum subarray sum
        return max_so_far;
    }
 
    // Function to find Minimum Sum after replacement
    const findMaxSum = (nums1, nums2) => {
        let n = nums1.length;
        let s = new Array(n).fill(0), t = new Array(n).fill(0);
 
        // Calculating Sum of nums1 and nums2
        let S1 = 0, S2 = 0;
        for (let i = 0; i < n; i++) {
            S1 += nums1[i];
            S2 += nums2[i];
        }
 
        // Creating difference arrays
        for (let i = 0; i < n; i++) {
            t[i] = nums1[i] - nums2[i];
            s[i] = nums2[i] - nums1[i];
        }
 
        // Return Min Sum
        return Math.min(S2 - maxSubArraySum(s),
            S1 - maxSubArraySum(t));
    }
 
    // Driver Code
    let A = [10, 30, 10, 60, 20];
    let B = [40, 10, 40, 30, 10];
 
    // Function Call
    document.write(findMaxSum(A, B));
 
    // This code is contributed by rakeshsahni
 
</script>

90

Tiempo Complejidad : O(N)
Espacio Auxiliar : O(N)