Given an unsorted of distinct integers, find the largest pair sum in it. For example, the largest pair sum in {12, 34, 10, 6, 40} is 74.
Difficulty Level: Rookie
Expected Time Complexity: O(n) [Only one traversal of array is allowed]
This problem mainly boils down to finding the largest and second largest element in array. We can find the largest and second largest in O(n) time by traversing array once.
1) Initialize both first and second largest
first = max(arr[0], arr[1])
second = min(arr[0], arr[1])
2) Loop through remaining elements (from 3rd to end)
a) If the current element is greater than first, then update first
and second.
b) Else if the current element is greater than second then update
second
3) Return (first + second)
Below is the implementation of above algorithm:
C++
// C++ program to find largest pair sum in a given array #include<iostream> using namespace std; /* Function to return largest pair sum. Assumes that there are at-least two elements in arr[] */int findLargestSumPair(int arr[], int n) { // Initialize first and second largest element int first, second; if (arr[0] > arr[1]) { first = arr[0]; second = arr[1]; } else { first = arr[1]; second = arr[0]; } // Traverse remaining array and find first and second largest // elements in overall array for (int i = 2; i<n; i ++) { /* If current element is greater than first then update both first and second */ if (arr[i] > first) { second = first; first = arr[i]; } /* If arr[i] is in between first and second then update second */ else if (arr[i] > second && arr[i] != first) second = arr[i]; } return (first + second); } /* Driver program to test above function */int main() { int arr[] = {12, 34, 10, 6, 40}; int n = sizeof(arr)/sizeof(arr[0]); cout << "Max Pair Sum is " << findLargestSumPair(arr, n); return 0; } |
Java
// Java program to find largest pair sum in a given array class Test { static int arr[] = new int[]{12, 34, 10, 6, 40}; /* Method to return largest pair sum. Assumes that there are at-least two elements in arr[] */ static int findLargestSumPair() { // Initialize first and second largest element int first, second; if (arr[0] > arr[1]) { first = arr[0]; second = arr[1]; } else { first = arr[1]; second = arr[0]; } // Traverse remaining array and find first and second largest // elements in overall array for (int i = 2; i<arr.length; i ++) { /* If current element is greater than first then update both first and second */ if (arr[i] > first) { second = first; first = arr[i]; } /* If arr[i] is in between first and second then update second */ else if (arr[i] > second && arr[i] != first) second = arr[i]; } return (first + second); } // Driver method to test the above function public static void main(String[] args) { System.out.println("Max Pair Sum is " + findLargestSumPair()); } } |
Python3
# Python3 program to find largest # pair sum in a given array # Function to return largest pair # sum. Assumes that there are # at-least two elements in arr[] def findLargestSumPair(arr, n): # Initialize first and second # largest element if arr[0] > arr[1]: first = arr[0] second = arr[1] else: first = arr[1] second = arr[0] # Traverse remaining array and # find first and second largest # elements in overall array for i in range(2, n): # If current element is greater # than first then update both # first and second if arr[i] > first: second = first first = arr[i] # If arr[i] is in between first # and second then update second elif arr[i] > second and arr[i] != first: second = arr[i] return (first + second) # Driver program to test above function */ arr = [12, 34, 10, 6, 40] n = len(arr) print("Max Pair Sum is", findLargestSumPair(arr, n)) # This code is contributed by Smitha Dinesh Semwal |
C#
// C# program to find largest // pair sum in a given array using System; class GFG { /* Method to return largest pair sum. Assumes that there are at-least two elements in arr[] */ static int findLargestSumPair(int []arr) { // Initialize first and // second largest element int first, second; if (arr[0] > arr[1]) { first = arr[0]; second = arr[1]; } else { first = arr[1]; second = arr[0]; } // Traverse remaining array and // find first and second largest // elements in overall array for (int i = 2; i < arr.Length; i ++) { /* If current element is greater than first then update both first and second */ if (arr[i] > first) { second = first; first = arr[i]; } /* If arr[i] is in between first and second then update second */ else if (arr[i] > second && arr[i] != first) second = arr[i]; } return (first + second); } // Driver Code public static void Main() { int []arr1 = new int[]{12, 34, 10, 6, 40}; Console.Write("Max Pair Sum is " + findLargestSumPair(arr1)); } } |
PHP
<?php // PHP program to find largest // pair sum in a given array // Function to return largest // pair sum. Assumes that // there are at-least two // elements in arr[] */ function findLargestSumPair($arr, $n) { // Initialize first and // second largest element $first; $second; if ($arr[0] > $arr[1]) { $first = $arr[0]; $second = $arr[1]; } else { $first = $arr[1]; $second = $arr[0]; } // Traverse remaining array // and find first and second // largest elements in overall // array for ( $i = 2; $i<$n; $i ++) { // If current element is greater // than first then update both // first and second if ($arr[$i] > $first) { $second = $first; $first = $arr[$i]; } // If arr[i] is in between first // and second then update second else if ($arr[$i] > $second and $arr[$i] != $first) $second = $arr[$i]; } return ($first + $second); } // Driver Code $arr = array(12, 34, 10, 6, 40); $n = count($arr); echo "Max Pair Sum is " , findLargestSumPair($arr, $n); // This code is contributed by anuj_67. ?> |
Output :
Max Pair Sum is 74
Time complexity of above solution is O(n).
leave a comment
0 Comments