Find the largest pair sum in an unsorted array

The problem you're tackling involves finding the largest sum that can be obtained by adding two numbers from an unsorted array. Specifically, you need to find the two largest elements in the array and calculate their sum.

Problem Statement

Given an unsorted array of integers, the task is to find the largest possible sum of any two numbers from the array.

Example

Consider the array arr = [6, 2, 9, 5, -2, 4, 8, 2, 7, 1, 3].

The largest pair sum is obtained by adding the largest elements, which are 9 and 8. Thus, the largest sum is 17.

Idea to Solve

To find the largest pair sum, you need to identify the two largest elements in the array. One approach is to iterate through the array and maintain indices for the two largest elements encountered so far. By the end of the iteration, you will have identified the two largest elements, and their sum will be the largest pair sum.

Algorithm

1. Create a function largest_sum(arr[], size):
   • Initialize variables first and second to hold indices of the two largest elements.
   • Iterate through the array:
     • If the current element is greater than the element at index first, update first with the current index.
     • If the current element is greater than the element at index second, update second with the current index.
   • Display the largest pair sum, which is the sum of arr[first] and arr[second].

Pseudocode

function largest_sum(arr[], size):
    if size <= 1:
        return
    
    first = 0
    second = size - 1
    
    for i from 0 to size - 1:
        if arr[i] > arr[first]:
            first = i
        if arr[i] > arr[second]:
            second = i
    
    display "(", arr[first], ",", arr[second], ") :", arr[first] + arr[second]

main():
    arr = [6, 2, 9, 5, -2, 4, 8, 2, 7, 1, 3]
    size = size of arr
    largest_sum(arr, size)

Program

• C
• C++
• Java
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4

//C Program
//Find the largest pair sum in an unsorted array
#include <stdio.h>


//Find the sum of largest pair in an unsorted array
void largest_sum(int arr[],int size)
{
  if(size<=1)
  {
    return;
  }

  //Set initial array index
  int first = 0;

  int second =size-1;

  for (int i = 0,j=size-1; i < size; ++i,j--)
  {
    if(i!=second && arr[i] > arr[first])
    {
      //When get a new max element 
      first = i;
    }
    if(j!=first && arr[j]>arr[second])
    {
      second=j;
    }
  }
  //Display the sum of two largest element
  printf("(%d ,%d) : %d\n",arr[first],arr[second] ,arr[first]+arr[second]);
}

int main()
{
  //Define the value of array elements
  int arr[] = {6,2,9,5,-2,4,8,2,7,1,3};

  //Get the size of array
  int size=sizeof(arr)/sizeof(arr[0]);

  largest_sum(arr,size);
  return 0;
}

(9 ,8) : 17

#include<iostream>

using namespace std;

/*
  C++ Program
  Find the largest pair sum in an unsorted array
*/
class MyArray {
	public:

		//Find the sum of largest pair in an unsorted array
		void largest_sum(int arr[], int size) {
			if (size <= 1) {
				return;
			}
			//Set initial array index
			int first = 0;
			int second = size - 1;
			for (int i = 0, j = size - 1; i < size; ++i, j--) {
				if (i != second && arr[i] > arr[first]) {
					//When get a new max element 
					first = i;
				}
				if (j != first && arr[j] > arr[second]) {
					second = j;
				}
			}
			//Display the sum of two largest element

			cout << "(" << arr[first] << " ," << arr[second] << ") : " << (arr[first] + arr[second]) << "\n";
		}
};
int main() {
	MyArray obj = MyArray();
	int arr[] = {
		6,
		2,
		9,
		5,
		-2,
		4,
		8,
		2,
		7,
		1,
		3
	};
	//Get the size of array
	int size = sizeof(arr) / sizeof(arr[0]);
	obj.largest_sum(arr, size);
	return 0;
}

(9 ,8) : 17

/*
  Java Program
  Find the largest pair sum in an unsorted array
*/

public class MyArray 
{
  //Find the sum of largest pair in an unsorted array
  public void largest_sum(int []arr,int size)
  {
    if(size<=1)
    {
      return;
    }

    //Set initial array index
    int first = 0;

    int second =size-1;

    for (int i = 0,j=size-1; i < size; ++i,j--)
    {
      if(i!=second && arr[i] > arr[first])
      {
        //When get a new max element 
        first = i;
      }
      if(j!=first && arr[j]>arr[second])
      {
        second=j;
      }
    }
    //Display the sum of two largest element
    System.out.print("("+arr[first]+" ,"+arr[second]+") : "+(arr[first]+arr[second])+"\n");
  }
  public static void main(String[] args) {

    MyArray obj = new MyArray();
    //Define the value of array elements
    int []arr = {6,2,9,5,-2,4,8,2,7,1,3};
    //Get the size of array
    int size = arr.length;
 
    obj.largest_sum(arr,size);
 
  }
}

(9 ,8) : 17

/*
  C# Program
  Find the largest pair sum in an unsorted array
*/

using System;


public class MyArray {
	//Find the sum of largest pair in an unsorted array
	public void largest_sum(int[] arr, int size) {
		if (size <= 1) {
			return;
		}
		//Set initial array index
		int first = 0;
		int second = size - 1;
		for (int i = 0, j = size - 1; i < size; ++i, j--) {
			if (i != second && arr[i] > arr[first]) {
				//When get a new max element 
				first = i;
			}
			if (j != first && arr[j] > arr[second]) {
				second = j;
			}
		}
		Console.Write("(" + arr[first] + " ," + arr[second] + ") : " + (arr[first] + arr[second]) + "\n");
	}
	public static void Main(String[] args) {
		MyArray obj = new MyArray();
		int[]
		//Define the value of array elements
		arr = {
			6,
			2,
			9,
			5,
			-2,
			4,
			8,
			2,
			7,
			1,
			3
		};
		//Get the size of array
		int size = arr.Length;
		obj.largest_sum(arr, size);
	}
}

(9 ,8) : 17

<?php
/*
  Php Program
  Find the largest pair sum in an unsorted array
*/
class MyArray {
	//Find the sum of largest pair in an unsorted array

	public 	function largest_sum($arr, $size) {
		if ($size <= 1) {
			return;
		}
		//Set initial array index
		$first = 0;
		$second = $size - 1;
		for ($i = 0, $j = $size - 1; $i < $size; ++$i, $j--) {
			if ($i != $second && $arr[$i] > $arr[$first]) {
				//When get a new max element 
				$first = $i;
			}
			if ($j != $first && $arr[$j] > $arr[$second]) {
				$second = $j;
			}
		}
		//Display the sum of two largest element

		echo("(". $arr[$first] ." ,". $arr[$second] .") : ". ($arr[$first] + $arr[$second]) ."\n");
	}
}

function main() {
	$obj = new MyArray();
	//Define the value of array elements
	$arr = array(6, 2, 9, 5, -2, 4, 8, 2, 7, 1, 3);
	//Get the size of array
	$size = count($arr);
	$obj->largest_sum($arr, $size);

}
main();

(9 ,8) : 17

/*
  Node Js Program
  Find the largest pair sum in an unsorted array
*/
class MyArray {
	//Find the sum of largest pair in an unsorted array
	largest_sum(arr, size) {
		if (size <= 1) {
			return;
		}

		//Set initial array index
		var first = 0;
		var second = size - 1;
		for (var i = 0,j = size - 1; i < size; ++i, j--) {
			if (i != second && arr[i] > arr[first]) {
				//When get a new max element 
				first = i;
			}

			if (j != first && arr[j] > arr[second]) {
				second = j;
			}
		}

		//Display the sum of two largest element

		process.stdout.write("(" + arr[first] + " ," + arr[second] + ") : " + (arr[first] + arr[second]) + "\n");
	}
}

function main(args) {
	var obj = new MyArray();
	//Define the value of array elements
	var arr = [6, 2, 9, 5, -2, 4, 8, 2, 7, 1, 3];
	//Get the size of array
	var size = arr.length;
	obj.largest_sum(arr, size);
}

main();

(9 ,8) : 17

# Python 3 Program
# Find the largest pair sum in an unsorted array
class MyArray :
	# Find the sum of largest pair in an unsorted array
	def largest_sum(self, arr, size) :
		if (size <= 1) :
			return
		
		first = 0
		second = size - 1
		i = 0
		j = size - 1
		while (i < size) :
			if (i != second and arr[i] > arr[first]) :
				# When get a new max element 
				first = i
			
			if (j != first and arr[j] > arr[second]) :
				second = j
			
			i += 1
			j -= 1
		
		print("(", arr[first] ," ,", arr[second] ,") : ", (arr[first] + arr[second]) ,"\n", end = "")
	

def main() :
	obj = MyArray()
	arr = [6, 2, 9, 5, -2, 4, 8, 2, 7, 1, 3]
	size = len(arr)
	obj.largest_sum(arr, size)


if __name__ == "__main__":
	main()

( 9  , 8 ) :  17

# Ruby Program
# Find the largest pair sum in an unsorted array
class MyArray 
	# Find the sum of largest pair in an unsorted array
	def largest_sum(arr, size) 
		if (size <= 1) 
			return
		end
		first = 0
		second = size - 1
		i = 0
		j = size - 1
		while (i < size) 
			if (i != second && arr[i] > arr[first]) 
				# When get a new max element 
				first = i
			end
			if (j != first && arr[j] > arr[second]) 
				second = j
			end
			i += 1
			j -= 1
		end
		print("(", arr[first] ," ,", arr[second] ,")  :", (arr[first] + arr[second]) ,"\n")
	end
end
def main() 
	obj = MyArray.new()
	arr = [6, 2, 9, 5, -2, 4, 8, 2, 7, 1, 3]
	size = arr.length
	obj.largest_sum(arr, size)
end
main()

(9 ,8)  :17

/*
  Scala Program
  Find the largest pair sum in an unsorted array
*/
class MyArray {
	//Find the sum of largest pair in an unsorted array
	def largest_sum(arr: Array[Int], size: Int): Unit = {
		if (size <= 1) {
			return;
		}
		var first: Int = 0;
		var second: Int = size - 1;
		var i: Int = 0;
		var j: Int = size - 1;
		while (i < size) {
			if (i != second && arr(i) > arr(first)) {
				//When get a new max element 
				first = i;
			}
			if (j != first && arr(j) > arr(second)) {
				second = j;
			}
			i += 1;
			j -= 1;
		}
		print("(" + arr(first) + " ," + arr(second) + ") : " + (arr(first) + arr(second)) + "\n");
	}
}
object Main {
	def main(args: Array[String]): Unit = {
		val obj: MyArray = new MyArray();
		val arr: Array[Int] = Array(6, 2, 9, 5, -2, 4, 8, 2, 7, 1, 3);
		val size: Int = arr.length;
		obj.largest_sum(arr, size);
	}
}

(9 ,8) : 17

/*
  Swift Program
  Find the largest pair sum in an unsorted array
*/
class MyArray {
	//Find the sum of largest pair in an unsorted array
	func largest_sum(_ arr: [Int], _ size: Int) {
		if (size <= 1) {
			return;
		}
		var first: Int = 0;
		var second: Int = size - 1;
		var i: Int = 0;
		var j: Int = size - 1;
		while (i < size) {
			if (i != second && arr[i] > arr[first]) {
				//When get a new max element 
				first = i;
			}
			if (j != first && arr[j] > arr[second]) {
				second = j;
			}
			i += 1;
			j -= 1;
		}
		print("(", arr[first] ,",", arr[second] ,") :", (arr[first] + arr[second]) ,"\n", terminator: "");
	}
}
func main() {
	let obj: MyArray = MyArray();
	let arr: [Int] = [6, 2, 9, 5, -2, 4, 8, 2, 7, 1, 3];
	let size: Int = arr.count;
	obj.largest_sum(arr, size);
}
main();

( 9 , 8 ) : 17

Time Complexity

The algorithm iterates through the array once, and each iteration takes constant time operations (comparisons and assignments). Therefore, the time complexity of the solution is O(n), where 'n' is the size of the array.

Result Explanation

The algorithm identifies the two largest elements in the array and calculates their sum, which represents the largest pair sum. In the example array, the largest elements are 9 and 8, and their sum is 17. The output line shows the largest pair along with its sum: (9, 8) : 17. This demonstrates how the algorithm effectively finds the largest pair sum in an unsorted array.