Given an array arr[] of distinct Integers, find the pair with maximum sum such that both elements of the pair are not adjacent in the array
Examples:
Input: arr[] = {7, 3, 4, 1, 8, 9}
Output: 9 7
Explanation: Pair with maximum sum is (8, 9).
But since both elements are adjacent, it is not a valid pair.
Therefore, the pair with maximum sum is (9, 7) with sum 16.Input: arr[] = {2, 1, 3}
Output: 2 3Input: arr[] = {4, 3, 7, 9, 8, 1}
Output: 7 8
Explanation: Sum of both the pairs {7, 9} and {9, 8} are greater.
But they are adjacent pairs. Hence this is the valid answer.
Approach: The Idea is to compute the indices of the largest three elements in the array. After computing the indices, check the pair with max sum and also check whether they are adjacent or not. It is always possible to get at least one pair with two elements that are not adjacent as the three largest elements have been computed.
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 max pair sum// which are non-adjacentpair<int, int> getMaxSumPair(int arr[], int N){ // Indices for storing first, second // and third largest element if (N < 3) { return make_pair(-1, -1); } int first, second, third; if (arr[1] > arr[0]) { if (arr[1] > arr[2]) { first = 1; if (arr[2] > arr[0]) { second = 2; third = 0; } else { second = 0; third = 2; } } else { first = 2; second = 1; third = 0; } } else { if (arr[0] > arr[2]) { first = 0; if (arr[2] > arr[1]) { second = 2; third = 1; } else { second = 1; third = 2; } } else { first = 2; second = 0; third = 1; } } for (int i = 3; i < N; ++i) { if (arr[i] > arr[first]) { third = second; second = first; first = i; } else if (arr[i] > arr[second]) { third = second; second = i; } else if (arr[i] > arr[third]) { third = i; } } // Check whether the elements // are adjacent or not if (abs(first - second) == 1) { if (abs(first - third) == 1) { return make_pair(arr[second], arr[third]); } else { return make_pair(arr[first], arr[third]); } } else { return make_pair(arr[first], arr[second]); }}// Driver Codeint main(){ int arr[] = { 7, 3, 4, 1, 8, 9 }; int N = sizeof(arr) / sizeof(*arr); pair<int, int> p = getMaxSumPair(arr, N); cout << p.first << " " << p.second; return 0;} |
Java
// Java program for the above approachimport java.io.*;public class GFG { static class Pair { int first; int second; public Pair(int first, int second) { this.first = first; this.second = second; } } // Function to find the max pair sum // which are non-adjacent static Pair getMaxSumPair(int arr[], int N) { // Indices for storing first, second // and third largest element if (N < 3) { return new Pair(-1, -1); } int first, second, third; if (arr[1] > arr[0]) { if (arr[1] > arr[2]) { first = 1; if (arr[2] > arr[0]) { second = 2; third = 0; } else { second = 0; third = 2; } } else { first = 2; second = 1; third = 0; } } else { if (arr[0] > arr[2]) { first = 0; if (arr[2] > arr[1]) { second = 2; third = 1; } else { second = 1; third = 2; } } else { first = 2; second = 0; third = 1; } } for (int i = 3; i < N; ++i) { if (arr[i] > arr[first]) { third = second; second = first; first = i; } else if (arr[i] > arr[second]) { third = second; second = i; } else if (arr[i] > arr[third]) { third = i; } } // Check whether the elements // are adjacent or not if (Math.abs(first - second) == 1) { if (Math.abs(first - third) == 1) { return new Pair(arr[second], arr[third]); } else { return new Pair(arr[first], arr[third]); } } else { return new Pair(arr[first], arr[second]); } } // Driver Code public static void main(String args[]) { int arr[] = { 7, 3, 4, 1, 8, 9 }; int N = arr.length; Pair p = getMaxSumPair(arr, N); System.out.println(p.first + " " + p.second); }}// This code is contributed by saurabh_jaiswal. |
Python3
# Python code for the above approach# Function to find the max pair sum# which are non-adjacentdef getMaxSumPair(arr, N): # Indices for storing first, second # and third largest element if (N < 3): return [-1, -1] first = second = third = None if (arr[1] > arr[0]): if (arr[1] > arr[2]): first = 1 if (arr[2] > arr[0]): second = 2 third = 0 else: second = 0 third = 2 else: first = 2 second = 1 third = 0 else: if (arr[0] > arr[2]): first = 0 if (arr[2] > arr[1]): second = 2 third = 1 else: second = 1 third = 2 else: first = 2 second = 0 third = 1 for i in range(3, N): if (arr[i] > arr[first]): third = second second = first first = i elif (arr[i] > arr[second]): third = second second = i elif (arr[i] > arr[third]): third = i # Check whether the elements # are adjacent or not if (abs(first - second) == 1): if (abs(first - third) == 1): return [arr[second], arr[third]] else: return [arr[first], arr[third]] else: return [arr[first], arr[second]]# Driver Codearr = [7, 3, 4, 1, 8, 9]N = len(arr)p = getMaxSumPair(arr, N)print(f"{p[0]} {p[1]}")# This code is contributed by Saurabh Jaiswal |
C#
// C# program for the above approachusing System;public class GFG { class Pair { public int first; public int second; public Pair(int first, int second) { this.first = first; this.second = second; } } // Function to find the max pair sum // which are non-adjacent static Pair getMaxSumPair(int []arr, int N) { // Indices for storing first, second // and third largest element if (N < 3) { return new Pair(-1, -1); } int first, second, third; if (arr[1] > arr[0]) { if (arr[1] > arr[2]) { first = 1; if (arr[2] > arr[0]) { second = 2; third = 0; } else { second = 0; third = 2; } } else { first = 2; second = 1; third = 0; } } else { if (arr[0] > arr[2]) { first = 0; if (arr[2] > arr[1]) { second = 2; third = 1; } else { second = 1; third = 2; } } else { first = 2; second = 0; third = 1; } } for (int i = 3; i < N; ++i) { if (arr[i] > arr[first]) { third = second; second = first; first = i; } else if (arr[i] > arr[second]) { third = second; second = i; } else if (arr[i] > arr[third]) { third = i; } } // Check whether the elements // are adjacent or not if (Math.Abs(first - second) == 1) { if (Math.Abs(first - third) == 1) { return new Pair(arr[second], arr[third]); } else { return new Pair(arr[first], arr[third]); } } else { return new Pair(arr[first], arr[second]); } } // Driver Code public static void Main(String []args) { int []arr = { 7, 3, 4, 1, 8, 9 }; int N = arr.Length; Pair p = getMaxSumPair(arr, N); Console.WriteLine(p.first + " " + p.second); }}// This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript code for the above approach // Function to find the max pair sum // which are non-adjacent function getMaxSumPair(arr, N) { // Indices for storing first, second // and third largest element if (N < 3) { return [-1, -1]; } let first, second, third; if (arr[1] > arr[0]) { if (arr[1] > arr[2]) { first = 1; if (arr[2] > arr[0]) { second = 2; third = 0; } else { second = 0; third = 2; } } else { first = 2; second = 1; third = 0; } } else { if (arr[0] > arr[2]) { first = 0; if (arr[2] > arr[1]) { second = 2; third = 1; } else { second = 1; third = 2; } } else { first = 2; second = 0; third = 1; } } for (let i = 3; i < N; ++i) { if (arr[i] > arr[first]) { third = second; second = first; first = i; } else if (arr[i] > arr[second]) { third = second; second = i; } else if (arr[i] > arr[third]) { third = i; } } // Check whether the elements // are adjacent or not if (Math.abs(first - second) == 1) { if (Math.abs(first - third) == 1) { return [arr[second], arr[third]]; } else { return [arr[first], arr[third]]; } } else { return [arr[first], arr[second]]; } } // Driver Code let arr = [7, 3, 4, 1, 8, 9]; let N = arr.length; let p = getMaxSumPair(arr, N); document.write(p[0] + " " + p[1]); // This code is contributed by Potta Lokesh </script> |
Output
9 7
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
