Find the largest pair sum in an unsorted array
Last Updated :
26 Sep, 2023
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
Brute Force Approach:
Brute force approach to solve this problem would be to use two nested loops to iterate over all possible pairs of integers in the array, compute their sum and keep track of the maximum sum encountered so far. The time complexity of this approach would be O(n^2).
Below is implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int findLargestSumPair(int arr[], int n)
{
int maxSum = INT_MIN;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
int sum = arr[i] + arr[j];
if (sum > maxSum) {
maxSum = sum;
}
}
}
return maxSum;
}
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
import java.util.*;
public class Main
{
static int findLargestSumPair(int[] arr, int n) {
int maxSum = Integer.MIN_VALUE;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
int sum = arr[i] + arr[j];
if (sum > maxSum) {
maxSum = sum;
}
}
}
return maxSum;
}
public static void main(String[] args) {
int[] arr = {12, 34, 10, 6, 40};
int n = arr.length;
System.out.println("Max Pair Sum is " + findLargestSumPair(arr, n));
}
}
|
Python3
import sys
def findLargestSumPair(arr, n):
maxSum = -sys.maxsize - 1
for i in range(0, n - 1):
for j in range(i + 1, n):
sum = arr[i] + arr[j]
if (sum > maxSum):
maxSum = sum
return maxSum
if __name__ == '__main__':
arr = [12, 34, 10, 6, 40]
n = len(arr)
print("Max Pair Sum is", findLargestSumPair(arr, n))
|
C#
using System;
class Program
{
static int FindLargestSumPair(int[] arr, int n)
{
int maxSum = int.MinValue;
for (int i = 0; i < n - 1; i++)
{
for (int j = i + 1; j < n; j++)
{
int sum = arr[i] + arr[j];
if (sum > maxSum)
{
maxSum = sum;
}
}
}
return maxSum;
}
static void Main(string[] args)
{
int[] arr = { 12, 34, 10, 6, 40 };
int n = arr.Length;
Console.WriteLine("Max Pair Sum is " + FindLargestSumPair(arr, n));
}
}
|
Javascript
function findLargestSumPair(arr) {
let maxSum = Number.MIN_SAFE_INTEGER;
for (let i = 0; i < arr.length - 1; i++) {
for (let j = i + 1; j < arr.length; j++) {
let sum = arr[i] + arr[j];
if (sum > maxSum) {
maxSum = sum;
}
}
}
return maxSum;
}
let arr = [12, 34, 10, 6, 40];
let maxPairSum = findLargestSumPair(arr);
console.log("Max Pair Sum is " + maxPairSum);
|
Output
Max Pair Sum is 74
Time Complexity: O(N^2)
Auxiliary Space: O(1)
This problem mainly boils down to finding the largest and second-largest element in an array. We can find the largest and second-largest in O(n) time by traversing the array once.
1) Initialize the
first = Integer.MIN_VALUE
second = Integer.MIN_VALUE
2) Loop through the elements
a) If the current element is greater than the first max element, then update second max to the first
max and update the first max to the current element.
3) Return (first + second)
Below is the implementation of the above algorithm:
C++
#include <iostream>
using namespace std;
int findLargestSumPair(int arr[], int n)
{
int first, second;
if (arr[0] > arr[1]) {
first = arr[0];
second = arr[1];
}
else {
first = arr[1];
second = arr[0];
}
for (int i = 2; i < n; i++) {
if (arr[i] > first) {
second = first;
first = arr[i];
}
else if (arr[i] > second && arr[i] != first)
second = arr[i];
}
return (first + second);
}
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
public class LargestPairSum {
public static void main(String[] args)
{
int arr[] = { 12, 34, 10, 6, 40};
System.out.println(largestPairSum(arr, arr.length));
}
private static int largestPairSum(int[] arr, int n)
{
int j = 0;
int max = n == 1 ? arr[0] + arr[1] : arr[0];
for (int i = 0; i < n; i++) {
int sum = arr[j] + arr[i];
if (sum > max) {
max = sum;
if (arr[j] < arr[i]) {
j = i;
}
}
}
return max;
}
}
/**
* This code is contributed by Tanveer Baba
*/
|
Python3
def findLargestSumPair(arr, n):
if arr[0] > arr[1]:
first = arr[0]
second = arr[1]
else:
first = arr[1]
second = arr[0]
for i in range(2, n):
if arr[i] > first:
second = first
first = arr[i]
elif arr[i] > second and arr[i] != first:
second = arr[i]
return (first + second)
arr = [12, 34, 10, 6, 40]
n = len(arr)
print("Max Pair Sum is",
findLargestSumPair(arr, n))
|
C#
using System;
class GFG {
static int findLargestSumPair(int[] arr)
{
int first, second;
if (arr[0] > arr[1]) {
first = arr[0];
second = arr[1];
}
else {
first = arr[1];
second = arr[0];
}
for (int i = 2; i < arr.Length; i++) {
if (arr[i] > first) {
second = first;
first = arr[i];
}
else if (arr[i] > second && arr[i] != first)
second = arr[i];
}
return (first + second);
}
public static void Main()
{
int[] arr1 = new int[] { 12, 34, 10, 6, 40 };
Console.Write("Max Pair Sum is "
+ findLargestSumPair(arr1));
}
}
|
Javascript
<script>
function findLargestSumPair(arr)
{
let first, second;
if (arr[0] > arr[1])
{
first = arr[0];
second = arr[1];
}
else
{
first = arr[1];
second = arr[0];
}
for (let i = 2; i < arr.length; i ++)
{
if (arr[i] > first)
{
second = first;
first = arr[i];
}
else if (arr[i] > second &&
arr[i] != first)
second = arr[i];
}
return (first + second);
}
let arr1 = [12, 34, 10, 6, 40];
document.write("Max Pair Sum is " + findLargestSumPair(arr1));
</script>
|
PHP
<?php
function findLargestSumPair($arr, $n)
{
$first;
$second;
if ($arr[0] > $arr[1])
{
$first = $arr[0];
$second = $arr[1];
}
else
{
$first = $arr[1];
$second = $arr[0];
}
for ( $i = 2; $i<$n; $i ++)
{
if ($arr[$i] > $first)
{
$second = $first;
$first = $arr[$i];
}
else if ($arr[$i] > $second and
$arr[$i] != $first)
$second = $arr[$i];
}
return ($first + $second);
}
$arr = array(12, 34, 10, 6, 40);
$n = count($arr);
echo "Max Pair Sum is "
, findLargestSumPair($arr, $n);
?>
|
Output
Max Pair Sum is 74
The time complexity of the above solution is O(n).
The space complexity of the above solution is O(1).
Please Login to comment...