Maximum sum of pairs that are at least K distance apart in an array
Given an array arr[] consisting of N integers and an integer K, the task is to find the maximum sum of pairs of elements that are separated by at least K indices.
Examples:
Input: arr[] = {2, 4, 1, 6, 8}, K = 2
Output: 12
Explanation:
The elements {1, 4} are K(= 2) distance apart. The sum of pairs {4, 8} is 4 + 8 = 12, which is maximum.Input: arr[] = {1, 2, 3}, K = 1
Output: 4
Naive Approach: The simplest approach to solve the given problem is to generate all possible pairs of the given array which are K distant apart and print the maximum sum among all possible pairs formed.
Time Complexity: O(N2)
Auxiliary Space: O(1), since no extra space has been taken.
Efficient Approach: The above approach can be optimized by precomputing the prefix maximums for each array element. Follow the steps below to solve the given problem:
- Initialize a variable, say res as INT_MIN, that stores the maximum sum of valid pairs which are K distant apart in the given array.
- Initialize an array, say preMax[], that stores the maximum value array element up to each index i.
- Initialize preMax[0] equal to arr[0].
- Traverse the array over the range [1, N – 1] and update the value of preMax[i] to the maximum of preMax[i – 1] and arr[i].
- Now, iterate over the range [K, N – 1], and for each index i, update the value of res as the maximum of res and (arr[i] + preMax[i – K]).
- After completing the above steps, print the value of res as the result.
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 largest sum // pair that are K distant apart int getMaxPairSum( int arr[], int N, int K) { // Stores the prefix maximum array int preMax[N]; // Base Case preMax[0] = arr[0]; // Traverse the array and update // the maximum value upto index i for ( int i = 1; i < N; i++) { preMax[i] = max(preMax[i - 1], arr[i]); } // Stores the maximum sum of pairs int res = INT_MIN; // Iterate over the range [K, N] for ( int i = K; i < N; i++) { // Find the maximum value of // the sum of valid pairs res = max(res, arr[i] + preMax[i - K]); } // Return the resultant sum return res; } // Driver Code int main() { int arr[] = { 1, 2, 4, 8, 6, 3 }; int K = 3; int N = sizeof (arr) / sizeof (arr[0]); cout << getMaxPairSum(arr, N, K); return 0; } |
Java
// java program for the above approach import java.io.*; import java.lang.*; import java.util.*; public class GFG { // Function to find the largest sum // pair that are K distant apart static int getMaxPairSum( int [] arr, int N, int K) { // Stores the prefix maximum array int [] preMax = new int [N]; // Base Case preMax[ 0 ] = arr[ 0 ]; // Traverse the array and update // the maximum value upto index i for ( int i = 1 ; i < N; i++) { preMax[i] = Math.max(preMax[i - 1 ], arr[i]); } // Stores the maximum sum of pairs int res = Integer.MIN_VALUE; // Iterate over the range [K, N] for ( int i = K; i < N; i++) { // Find the maximum value of // the sum of valid pairs res = Math.max(res, arr[i] + preMax[i - K]); } // Return the resultant sum return res; } // Driver Code public static void main(String[] args) { int [] arr = { 1 , 2 , 4 , 8 , 6 , 3 }; int K = 3 ; int N = arr.length; System.out.print(getMaxPairSum(arr, N, K)); } } // This code is contributed by Kingash |
Python3
# Python3` program for the above approach # Function to find the largest sum # pair that are K distant apart def getMaxPairSum(arr, N, K): # Stores the prefix maximum array preMax = [ 0 ] * N # Base Case preMax[ 0 ] = arr[ 0 ] # Traverse the array and update # the maximum value upto index i for i in range ( 1 , N): preMax[i] = max (preMax[i - 1 ], arr[i]) # Stores the maximum sum of pairs res = - 10 * * 8 # Iterate over the range [K, N] for i in range (K, N): # Find the maximum value of # the sum of valid pairs res = max (res, arr[i] + preMax[i - K]) # Return the resultant sum return res # Driver Code if __name__ = = '__main__' : arr = [ 1 , 2 , 4 , 8 , 6 , 3 ] K = 3 N = len (arr) print (getMaxPairSum(arr, N, K)) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approach using System; class GFG { // Function to find the largest sum // pair that are K distant apart static int getMaxPairSum( int [] arr, int N, int K) { // Stores the prefix maximum array int [] preMax = new int [N]; // Base Case preMax[0] = arr[0]; // Traverse the array and update // the maximum value upto index i for ( int i = 1; i < N; i++) { preMax[i] = Math.Max(preMax[i - 1], arr[i]); } // Stores the maximum sum of pairs int res = Int32.MinValue; // Iterate over the range [K, N] for ( int i = K; i < N; i++) { // Find the maximum value of // the sum of valid pairs res = Math.Max(res, arr[i] + preMax[i - K]); } // Return the resultant sum return res; } // Driver Code public static void Main() { int [] arr = { 1, 2, 4, 8, 6, 3 }; int K = 3; int N = arr.Length; Console.Write(getMaxPairSum(arr, N, K)); } } // This code is contributed by ukasp. |
Javascript
<script> // Javascript program for the above approach // Function to find the largest sum // pair that are K distant apart function getMaxPairSum(arr, N, K) { // Stores the prefix maximum array var preMax = Array(N); // Base Case preMax[0] = arr[0]; // Traverse the array and update // the maximum value upto index i for ( var i = 1; i < N; i++) { preMax[i] = Math.max(preMax[i - 1], arr[i]); } // Stores the maximum sum of pairs var res = -1000000000; // Iterate over the range [K, N] for ( var i = K; i < N; i++) { // Find the maximum value of // the sum of valid pairs res = Math.max(res, arr[i] + preMax[i - K]); } // Return the resultant sum return res; } // Driver Code var arr = [1, 2, 4, 8, 6, 3]; var K = 3; var N = arr.length; document.write( getMaxPairSum(arr, N, K)); </script> |
9
Time Complexity: O(N)
Auxiliary Space: O(N)