two pairs with same max sum

Revision en1, by acash, 2020-01-04 23:42:18

Given an array a[].Find the two pairs (a,b) and (c,d) such that a+b==c+d.And the sum (a+b==c+d)value as maximum as possible Note->NO cpp only c language allowed which makes this problem more difficult for me

Example: N = 6, S[] = { 2, 3, 6, 4, 1, 5 } You can select pair of (6, 3) and (5, 4), two numbers can be same ,but same number can not be part of both pair.

My Thinking 1 -> I tried to make all possible pairs store the pairs sum in sorted array ,then i started searching form end to check if it is possible that we can find two teams with maxsum But unable to handle like case 0 0 1 1(which contain duplicates)

My Thinking 2 ->all ways to choose 1st, 2nd and 3rd student and check whether you have 4th one with skill equal to (S1+S2−S3)? And then choose maximum among all possible teams. But since n<=500 it will be O(n^4) can give TLE.

please help!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English acash 2020-01-04 23:43:46 97
en1 English acash 2020-01-04 23:42:18 912 Initial revision (published)