Max-distance sub-sequence

MAX-DISTANCE SUB-SEQUENCE

• Given N elements (2≤ N ≤100,000) on a straight line at positions x1,…, xn (0≤ x ≤1,000,000,000)
• The distance of a subset of N elements is defined to be the minimum distance between two elements
• Find the subset of N given elements containing exactly C elements such that the distance is maximal.
• Input
• The first line contains a positive integer T (1 <= T <= 20) which is the number of test cases.
• Subsequent lines are T test cases with the following format:
• Line 1: Two space-separated integers: N and C
• Lines 2: contains x1, x2 , . . , xn
• Output
• For each test case output one integer: the distance of the subset found.

MAX-DISTANCE SUB-SEQUENCE

• Example