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;
}
Try It

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;
}
Try It

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;
}
Try It


Next > < Prev
Scroll to Top