Monday, July 24, 2017

Find the largest pair sum in an unsorted array


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

No comments:

Post a Comment