Maximum sum of pairs that are at least K distance apart in an array

0 0 5 minutes read

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(N²)
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>

Output:

Time Complexity: O(N)
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!