Maximice la suma máxima posible de subarreglo de un arreglo intercambiando con elementos de otro arreglo

Dadas dos arrays arr[] y brr[] que constan de N y K elementos respectivamente, la tarea es encontrar la suma máxima posible de subarreglo de la array arr[] intercambiando cualquier elemento de la array arr[] con cualquier elemento de la array brr[] cualquier número de veces.

Ejemplos: 

Entrada: N = 5, K = 4, arr[] = { 7, 2, -1, 4, 5 }, brr[] = { 1, 2, 3, 2 }
Salida: 21
Explicación: Intercambiar arr[2] con brr[2] modifica arr[] a {7, 2, 3, 4, 5} 
Suma máxima de subarreglo del arreglo arr[] = 21

Entrada: N = 2, K = 2, arr[] = { -4, -4 }, brr[] = { 8, 8 }
Salida: 16
Explicación: Intercambiar arr[0] con brr[0] y arr[1 ] con brr[1] modifica arr[] a {8, 8}
Subarreglo de suma máxima del arreglo arr[] = 16

Enfoque: La idea para resolver este problema es que al intercambiar elementos de la array arr y brr, los elementos dentro de arr también se pueden intercambiar en tres intercambios. A continuación se presentan algunas observaciones:

• Si se necesita intercambiar dos elementos en el arreglo arr[] que tienen índices i y j , entonces tome cualquier elemento temporal del arreglo brr[], digamos en el índice k , y realice las siguientes operaciones:
  • Intercambiar arr[i] y brr[k].
  • Intercambiar brr[k] y arr[j].
  • Intercambiar arr[i] y brr[k].
• Ahora los elementos entre la array arr[] y brr[] también se pueden intercambiar dentro de la array arr[] . Por lo tanto, organice con avidez los elementos en la array arr[] de manera que contenga todos los enteros positivos de manera continua.

Siga los pasos a continuación para resolver el problema: 

• Almacene todos los elementos de la array arr[] y brr[] en otra array crr[] .
• Ordene la array crr[]  en orden descendente .
• Calcule la suma hasta el último índice ( menor que N ) en la array crr[] que contiene un elemento positivo.
• Imprime la suma obtenida.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum subarray sum
// possible by swapping elements from array
// arr[] with that from array brr[]
void maxSum(int* arr, int* brr, int N, int K)
{
    // Stores elements from the
    // arrays arr[] and brr[]
    vector<int> crr;
 
    // Store elements of array arr[]
    // and brr[] in the vector crr
    for (int i = 0; i < N; i++) {
        crr.push_back(arr[i]);
    }
    for (int i = 0; i < K; i++) {
        crr.push_back(brr[i]);
    }
 
    // Sort the vector crr
    // in descending order
    sort(crr.begin(), crr.end(),
         greater<int>());
 
    // Stores maximum sum
    int sum = 0;
 
    // Calculate the sum till the last
    // index in crr[] which is less than
    // N which contains a positive element
    for (int i = 0; i < N; i++) {
        if (crr[i] > 0) {
            sum += crr[i];
        }
        else {
            break;
        }
    }
 
    // Print the sum
    cout << sum << endl;
}
 
// Driver code
int main()
{
    // Given arrays and respective lengths
    int arr[] = { 7, 2, -1, 4, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int brr[] = { 1, 2, 3, 2 };
    int K = sizeof(brr) / sizeof(brr[0]);
 
    // Calculate maximum subarray sum
    maxSum(arr, brr, N, K);
}

// Java program for the above approach
import java.util.*;
class GFG
{
 
  // Function to find the maximum subarray sum
  // possible by swapping elements from array
  // arr[] with that from array brr[]
  static void maxSum(int arr[], int brr[], int N, int K)
  {
 
    // Stores elements from the
    // arrays arr[] and brr[]
    Vector<Integer> crr = new Vector<Integer>();
 
    // Store elements of array arr[]
    // and brr[] in the vector crr
    for (int i = 0; i < N; i++)
    {
      crr.add(arr[i]);
    }
    for (int i = 0; i < K; i++)
    {
      crr.add(brr[i]);
    }
 
    // Sort the vector crr
    // in descending order
    Collections.sort(crr);
    Collections.reverse(crr);
 
    // Stores maximum sum
    int sum = 0;
 
    // Calculate the sum till the last
    // index in crr[] which is less than
    // N which contains a positive element
    for (int i = 0; i < N; i++)
    {
      if (crr.get(i) > 0)
      {
        sum += crr.get(i);
      }
      else
      {
        break;
      }
    }
 
    // Print the sum
    System.out.println(sum);
  }
 
  // Driver code
  public static void main(String[] args)
  {
 
    // Given arrays and respective lengths
    int arr[] = { 7, 2, -1, 4, 5 };
    int N = arr.length;
    int brr[] = { 1, 2, 3, 2 };
    int K = brr.length;
 
    // Calculate maximum subarray sum
    maxSum(arr, brr, N, K);
  }
}
 
// This code is contributed by divyesh072019

# Python3 program for the above approach
 
# Function to find the maximum subarray sum
# possible by swapping elements from array
# arr[] with that from array brr[]
def maxSum(arr, brr, N, K):
     
    # Stores elements from the
    # arrays arr[] and brr[]
    crr = []
 
    # Store elements of array arr[]
    # and brr[] in the vector crr
    for i in range(N):
        crr.append(arr[i])
 
    for i in range(K):
        crr.append(brr[i])
 
    # Sort the vector crr
    # in descending order
    crr = sorted(crr)[::-1]
 
    # Stores maximum sum
    sum = 0
 
    # Calculate the sum till the last
    # index in crr[] which is less than
    # N which contains a positive element
    for i in range(N):
        if (crr[i] > 0):
            sum += crr[i]
        else:
            break
 
    # Print the sum
    print(sum)
 
# Driver code
if __name__ == '__main__':
     
    # Given arrays and respective lengths
    arr = [ 7, 2, -1, 4, 5 ]
    N = len(arr)
    brr = [ 1, 2, 3, 2 ]
    K = len(brr)
 
    # Calculate maximum subarray sum
    maxSum(arr, brr, N, K)
 
# This code is contributed by mohit kumar 29

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
     
// Function to find the maximum subarray sum
// possible by swapping elements from array
// arr[] with that from array brr[]
static void maxSum(int[] arr, int[] brr,
                   int N, int K)
{
     
    // Stores elements from the
    // arrays arr[] and brr[]
    List<int> crr = new List<int>();
  
    // Store elements of array arr[]
    // and brr[] in the vector crr
    for(int i = 0; i < N; i++)
    {
        crr.Add(arr[i]);
    }
    for(int i = 0; i < K; i++)
    {
        crr.Add(brr[i]);
    }
  
    // Sort the vector crr
    // in descending order
    crr.Sort();
    crr.Reverse();
  
    // Stores maximum sum
    int sum = 0;
  
    // Calculate the sum till the last
    // index in crr[] which is less than
    // N which contains a positive element
    for(int i = 0; i < N; i++)
    {
        if (crr[i] > 0)
        {
            sum += crr[i];
        }
        else
        {
            break;
        }
    }
  
    // Print the sum
    Console.WriteLine(sum);
}
 
// Driver Code
static void Main()
{
     
    // Given arrays and respective lengths
    int[] arr = { 7, 2, -1, 4, 5 };
    int N = arr.Length;
    int[] brr = { 1, 2, 3, 2 };
    int K = brr.Length;
     
    // Calculate maximum subarray sum
    maxSum(arr, brr, N, K);
}
}
 
// This code is contributed by divyeshrabadiya07

<script>
 
    // Javascript program for the above approach
     
    // Function to find the maximum subarray sum
    // possible by swapping elements from array
    // arr[] with that from array brr[]
    function maxSum(arr, brr, N, K)
    {
 
        // Stores elements from the
        // arrays arr[] and brr[]
        let crr = [];
 
        // Store elements of array arr[]
        // and brr[] in the vector crr
        for(let i = 0; i < N; i++)
        {
            crr.push(arr[i]);
        }
        for(let i = 0; i < K; i++)
        {
            crr.push(brr[i]);
        }
 
        // Sort the vector crr
        // in descending order
        crr.sort(function(a, b){return a - b});
        crr.reverse();
 
        // Stores maximum sum
        let sum = 0;
 
        // Calculate the sum till the last
        // index in crr[] which is less than
        // N which contains a positive element
        for(let i = 0; i < N; i++)
        {
            if (crr[i] > 0)
            {
                sum += crr[i];
            }
            else
            {
                break;
            }
        }
 
        // Print the sum
        document.write(sum);
    }
     
    // Given arrays and respective lengths
    let arr = [ 7, 2, -1, 4, 5 ];
    let N = arr.length;
    let brr = [ 1, 2, 3, 2 ];
    let K = brr.length;
      
    // Calculate maximum subarray sum
    maxSum(arr, brr, N, K);
 
</script>

21

Complejidad de tiempo: O((N+K)*log(N+K))
Espacio auxiliar: O(N+K)