# Find largest pair sum in unsorted array

## Find the maximum sum in an unsorted array formed by pair of elements

Given an array, finding the maximum sum formed by a pair of elements in that array.

### Example

INPUT

-6 12 16 6

OUTPUT

28

Here, the pair is 12,16 as their sum is maximum

## ALGORITHM 1

TIME COMPLEXITY – O(N)
SPACE COMPLEXITY – O(1)

1.    Simply take two variables to store the first maximum and second maximum of the array.
2.    Traverse the array.
3.    If an element is greater than first maximum then update it and make the previous value of first maximum as second maximum.
4.    If an element is smaller than first maximum but greater than second maximum then simply update second maximum.
5.    Final answer is the sum of first and second maximum respectively.

## C++ Program

``````#include <bits/stdc++.h>
using namespace std;

int main()
{
int arr[] = {27, 12, 15, 17, 19, 36}; //Array
int N = sizeof(arr)/sizeof(arr[0]); //size of array

int first = INT_MIN , second = INT_MIN;
//find the first and second largest number and their sum is the result
for(int i = 0 ; i<N; i++)
{
if(arr[i] > first)
{
if(first > second)
second = first;
first = arr[i];
}
else if(arr[i] > second)
second = arr[i];
}
cout << first + second;
return 0;
}``````

## ALGORITHM 2

TIME COMPLEXITY – O(NlogN)
SPACE COMPLEXITY – O(1)

1.    Simply sort the array.(Use merge sort or STL sort())
2.    Sum of the last two elements is the desired answer.

## C++ Program

``````#include <bits/stdc++.h>
using namespace std;

int main()
{
int arr[] = {27, 12, 15, 17, 19, 36}; //Array
int N = sizeof(arr)/sizeof(arr[0]); //size of array

sort(arr,arr+N);
cout<<(arr[N-1]+arr[N-2]);
return 0;
}``````

## ALGORITHM  3

TIME COMPLEXITY – O(N2)
SPACE COMPLEXITY – O(1)

1.    Simply run two loops.
2.    In first loop select an element
3.    In the inner loop find the sum of the present element and the selected element and check if it is maximum
4.    At end of two loops we will have the maximum sum.

## C++ Program

``````#include <bits/stdc++.h>
using namespace std;

int main()
{
int arr[] = {27, 12, 15, 17, 19, 36}; //Array
int N = sizeof(arr)/sizeof(arr[0]); //size of array
int max_sum = INT_MIN; //store final answer
for(int i=0;i<N;i++)
for(int j=i+1;j<N;j++)
if(arr[i] + arr[j] > max_sum)
max_sum = arr[i]+arr[j];

cout<<max_sum;
return 0;
}``````

Scroll to Top