Recursive (short) proof on the problem and Java code


  • 0
    M

    class Solution {
    public int arrayPairSum(int[] nums) {
    //proof of algorithm: nums.length=1->trivial
    //induction step: let second larget number in array be a, the largest be l. i.e. a<=l. then it is best to pair them together. suppose other kinda pairing, (a,c), (b,d). then sum for these four nums in this case would be c+d. if (a,b),(c,d) (assuming c<=d), sum=b+c. since b>=d, we know that pairing the largest two (a,b) gives the largest sum.
    Arrays.sort(nums);
    int sum=0;
    for(int i=0;i<nums.length/2;++i){
    sum+=nums[2*i];
    }
    return sum;
    }
    }


Log in to reply
 

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