Given an array arr[] consisting of N integers and an integer K, the task is to find the maximum sum of K pairs of the form (arr[i], arr[N – i – 1]), where (0 ? i ? N – 1).
Examples:
Input: arr[] = {2, -4, 3, -1, 2, 5}, K = 2
Output: 9
Explanation: All possibles pair of the form (arr[i], arr[N – i + 1]) are:
- (2, 5)
- (-1, 3)
- (-4, 2)
From the above pairs, the K(= 2) pairs with maximum sum are (2, 5) and (-1, 3). Therefore, maximum sum = 2 + 5 + (-1) + 3 = 9.
Input: arr[] = {2, -4, -2, 4}, K = 2
Output: 0
Naive Approach: The simplest approach to solve the problem is to generate all possible pairs of the given form from the array and calculate the maximum sum of K such pairs. After checking for all the pairs, print the maximum sum obtained among all the possible sums.
Time Complexity: O(N2 * K)
Auxiliary Space: O(N2)
Efficient Approach: The above approach can be optimized greedily. The idea is to choose only the K pairs with highest cost. Follow the steps below to solve the problem:
- Initialize a vector, say pairwiseSum[], to store the sums of required pairs from the array.
- Generate pairs (arr[i], arr[N – i + 1]) from the given array by traversing the array. Store their sums in the vector pairwiseSum[].
- Sort the vector pairwiseSum[] in descending order.
- After completing the above steps, print the sum of the first K elements of the vector pairwiseSum[] as the resultant sum.
Below is the implementation of the above approach:
C++
// 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 Codeint 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
// Java program for the above approachimport 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 Codepublic 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
# 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 Codeif __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#
// C# program for the above approachusing 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 Codepublic 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. |
Javascript
<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> |
Output:
9
Time Complexity: O(N * log N)
Auxiliary Space: O(N)
