package com.geekforgeeks.arrays;
import java.util.Arrays;
import java.util.Random;
/*
Problem: 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.
*/
public class FindLargestPairSumInSortedArray {
public static void main(String[] argv){
Random random = new Random();
int[] nums = new int[10];
for(int i = 0; i< 10; i++) {
nums[i]= random.nextInt(100);
}
System.out.println(Arrays.toString(nums));
FindLargestPairSumInSortedArray findLargestPairSumInSortedArray = new FindLargestPairSumInSortedArray();
int largestPairSumInSortedArray = findLargestPairSumInSortedArray.largestPairSumInSortedArray(nums);
Arrays.sort(nums);
int maxSum = nums[nums.length-1]+ nums[nums.length-2];
System.out.println(Arrays.toString(nums) + " " + maxSum);
System.out.println("Result "+ largestPairSumInSortedArray);
}
/*
Initialize the largest and second largest element in sorted array at the start and then iterate
through rest of the array
1) If the current element is less than second max continue
2) If the current element is greater than max, replace second max with max and max with current element
3) If not replace second max sum with the current element
*/
public int largestPairSumInSortedArray(int[] nums){
int max = Math.max(nums[0],nums[1]);
int secondMax = Math.min(nums[0],nums[1]);
for(int i = 2 ; i < nums.length; i++ ){
if(nums[i] <= secondMax)
continue;
if(nums[i] > max){
secondMax = max;
max =nums[i];
}else{
secondMax=nums[i];
}
}
return max+secondMax;
}
}
Monday, July 24, 2017
Find the largest pair sum in an unsorted array
Labels:
array,
designmanual,
geeksforgeeks
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment