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 apartint 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 Codeint 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 approachimport 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 apartdef 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 Codeif __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 approachusing 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 apartfunction 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 Codevar arr = [1, 2, 4, 8, 6, 3];var K = 3;var N = arr.length;document.write( getMaxPairSum(arr, N, K));</script> |
Output:
9
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
