Maximizar la suma de K pares formados por elementos que son equidistantes de ambos extremos de la array

Dada una array arr[] que consta de N enteros y un entero K , la tarea es encontrar la suma máxima de K pares de la forma (arr[i], arr[N – i – 1]) , donde (0 ≤ i ≤ norte – 1) .

Ejemplos:

Entrada: arr[] = {2, -4, 3, -1, 2, 5}, K = 2
Salida: 9
Explicación: Todos los pares posibles de la forma (arr[i], arr[N – i + 1] ) son:

1. (2, 5)
2. (-1, 3)
3. (-4, 2)

De los pares anteriores, los pares K(= 2) con suma máxima son (2, 5) y (-1, 3). Por tanto, suma máxima = 2 + 5 + (-1) + 3 = 9.

Entrada: arr[] = {2, -4, -2, 4}, K = 2
Salida: 0

Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los pares posibles de la forma dada a partir de la array y calcular la suma máxima de K tales pares. Después de verificar todos los pares, imprima la suma máxima obtenida entre todas las sumas posibles.

 Complejidad de Tiempo: O(N ² * K)
Espacio Auxiliar: O(N ² )

Enfoque eficiente: el enfoque anterior se puede optimizar con avidez . La idea es elegir solo los pares K con el costo más alto. Siga los pasos a continuación para resolver el problema:

• Inicialice un vector , digamos pairwiseSum[] , para almacenar las sumas de los pares requeridos de la array.
• Genere pares (arr[i], arr[N – i + 1]) a partir de la array dada atravesando la array . Almacene sus sumas en el vector pairwiseSum[] .
• Ordene el vector pairwiseSum[] en orden descendente .
• Después de completar los pasos anteriores, imprima la suma de los primeros K elementos del vector pairwiseSum[] como la suma resultante.

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 sum of
// K pairs of the form (arr[i],
// arr[N - i - 1])
int maxSum(int arr[], int N, int K)
{
    // Stores the resultant pairwise
    // sum
    vector<int> pairwiseSum;
 
    // Traverse till half of the array
    for (int i = 0; i < N / 2; i++) {
 
        // Update the value of curSum
        int curSum = arr[i] + arr[i + N / 2];
        pairwiseSum.push_back(curSum);
    }
 
    // Sort in the descending order
    sort(pairwiseSum.begin(),
         pairwiseSum.end(),
         greater<int>());
 
    // Stores the resultant maximum sum
    int maxSum = 0;
 
    // Add K maximum sums obtained
    for (int i = 0; i < K; i++) {
 
        // Update the value of maxSum
        maxSum += pairwiseSum[i];
    }
 
    // Print the maximum sum
    cout << maxSum;
}
 
// Driver Code
int main()
{
    int arr[] = { 2, -4, 3, 5, 2, -1 };
    int K = 2;
    int N = sizeof(arr) / sizeof(arr[0]);
    maxSum(arr, N, K);
 
    return 0;
}

// Java program for the above approach
import java.util.ArrayList;
import java.util.Collections;
class GFG{
 
// Function to find the maximum sum of
// K pairs of the form (arr[i],
// arr[N - i - 1])
public static void maxSum(int arr[], int N, int K)
{
    // Stores the resultant pairwise
    // sum
    ArrayList<Integer> pairwiseSum = new ArrayList<Integer>();
 
    // Traverse till half of the array
    for (int i = 0; i < N / 2; i++) {
 
        // Update the value of curSum
        int curSum = arr[i] + arr[i + N / 2];
        pairwiseSum.add(curSum);
    }
 
    // Sort in the descending order
    Collections.sort(pairwiseSum);
    Collections.reverse(pairwiseSum);
 
    // Stores the resultant maximum sum
    int maxSum = 0;
 
    // Add K maximum sums obtained
    for (int i = 0; i < K; i++) {
 
        // Update the value of maxSum
        maxSum += pairwiseSum.get(i);
    }
 
    // Print the maximum sum
    System.out.println(maxSum);
}
 
// Driver Code
public static void main(String args[])
{
    int arr[] = { 2, -4, 3, 5, 2, -1 };
    int K = 2;
    int N = arr.length;
    maxSum(arr, N, K);
}
}
 
// This code is contributed by gfgking.

# Python3 program for the above approach
 
# Function to find the maximum sum of
# K pairs of the form (arr[i],
# arr[N - i - 1])
def maxSum(arr, N, K):
     
    # Stores the resultant pairwise
    # sum
    pairwiseSum = []
 
    # Traverse till half of the array
    for i in range(N // 2):
         
        # Update the value of curSum
        curSum = arr[i] + arr[i + N // 2]
        pairwiseSum.append(curSum)
 
    # Sort in the descending order
    pairwiseSum.sort(reverse = True)
 
    # Stores the resultant maximum sum
    maxSum = 0
 
    # Add K maximum sums obtained
    for i in range(K):
         
        # Update the value of maxSum
        maxSum += pairwiseSum[i]
 
    # Print the maximum sum
    print(maxSum)
 
# Driver Code
if __name__ == '__main__':
     
    arr = [ 2, -4, 3, 5, 2, -1 ]
    K = 2
    N = len(arr)
     
    maxSum(arr, N, K)
 
# This code is contributed by bgangwar59

// C# program for the above approach
 
using System;
using System.Collections.Generic;
 
class GFG{
  
// Function to find the maximum sum of
// K pairs of the form (arr[i],
// arr[N - i - 1])
static void maxSum(int []arr, int N, int K)
{
    // Stores the resultant pairwise
    // sum
    List<int> pairwiseSum = new List<int>();
 
    // Traverse till half of the array
    for (int i = 0; i < N / 2; i++) {
 
        // Update the value of curSum
        int curSum = arr[i] + arr[i + N / 2];
        pairwiseSum.Add(curSum);
    }
 
    // Sort in the descending order
    pairwiseSum.Sort();
    pairwiseSum.Reverse();
    // Stores the resultant maximum sum
    int maxSum = 0;
 
    // Add K maximum sums obtained
    for (int i = 0; i < K; i++) {
 
        // Update the value of maxSum
        maxSum += pairwiseSum[i];
    }
 
    // Print the maximum sum
    Console.Write(maxSum);
}
 
// Driver Code
public static void Main()
{
    int []arr = { 2, -4, 3, 5, 2, -1 };
    int K = 2;
    int N = arr.Length;
    maxSum(arr, N, K);
 
}
}
 
// This code is contributed by ipg2016107.

<script>
 
      // JavaScript program for the above approach
 
 
      // Function to find the maximum sum of
      // K pairs of the form (arr[i],
      // arr[N - i - 1])
      function maxSum(arr, N, K) {
          // Stores the resultant pairwise
          // sum
          let pairwiseSum = [];
 
          // Traverse till half of the array
          for (let i = 0; i < N / 2; i++) {
 
              // Update the value of curSum
              let curSum = arr[i] + arr[i + parseInt(N / 2)];
              pairwiseSum.push(curSum);
          }
 
          // Sort in the descending order
          pairwiseSum.sort(function (a, b) { return b - a });
 
          // Stores the resultant maximum sum
         let maxSum = 0;
 
          // Add K maximum sums obtained
          for (let i = 0; i < K; i++) {
 
              // Update the value of maxSum
              maxSum += pairwiseSum[i];
          }
 
          // Print the maximum sum
          document.write(maxSum);
      }
 
      // Driver Code
 
      let arr = [2, -4, 3, 5, 2, -1];
      let K = 2;
      let N = arr.length;
      maxSum(arr, N, K);
 
// This code is contributed by Potta Lokesh
 
</script>

9

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