Layman's explaination


  • 0
    S
    • Let's say this is the array of size 2n = {a1,b1, a2,b2, a3,b3.... an,bn}

    • Desired result = Max [ Min(a1,b1) + Min(a2,b2) + Min(a3, b3)... Min(an,bn) ].

    • To max out Min(a1,b1) + Min(a2,b2) + Min(a3, b3)... Min(an,bn), you need to have every single one of these pairs as max as they can.

    • Now if you combine a big number with a small number and take their min, the outcome will be the smaller number. That's not gonna max out the external summation. The bigger number was sacrificed for no use.

    • To minimize the impact of the small numbers to the sum, take their min with their nearest numbers. This way, small numbers will only kill another small numbers, not the big ones.

    • To maximize the impact of the big numbers to the sum, take their min with their nearest numbers so that the big numbers are counted towards final summation.

    • Going by that logic, you would want the array to be sorted so that the numbers of similar magnitudes are placed next to each other.

    • Now its just a matter of taking the min of each consecutive pairs in a sorted array.

    • Since the array is already sorted, taking the first one in each of those pairs would suffice.

    public int arrayPairSum(int[] nums) {
    		Arrays.sort(nums);
    		int sum = 0;
    		for(int i=0; i<nums.length; i+=2)
                    {
    			sum = sum + nums[i];
    		}
    		return sum;
    	}
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.