CareerCup

Sort the array.
Consider a line-segment starting from (A[0],0) and ending at (A[n-1],0). Divide this line-segment into k-2 equal pieces. Find out the closest values to those pieces in the array A - these k values are the answer.

Not DP. Actually. The answer for 3 and 4 is different.
The solution for 3 is not necessary contained in the solution for 4.

greedy is the right track. O(nlgn) solution exist.

take diff from k for each number O(n) and then sort the numbers O(n log n)..then we can get the soln in O(k).

k < n < n log n...therefore overall order O(n log n)

I do not quite understand this problem. Can anybody elaborate a little bit (maybe through an example?) Thanks!

i think we can solve the problem by simply sorting it

>>> minimum difference of all the possible pairs of k numbers is maximum
wht does this mean? is it like sum of differences of all possible pairs of k numbers? Then sort the numbers and pick 1 minimum and (k-1) maximum numbers....

will sorting the numbers first and choosing the numbers from both ends in pairs give the maximum difference?

For example, suppose we have 5 numbers, 1, 8, 12, 16, 20 (sorted), when k=2, we can choose: 1 and 20, because they give the maximum distance. When k=3, we can choose any numbers in 8, 12, and 16, because 1, 20, and this number give the same total difference. When k=4, if we want to get the maximum difference, the 3rd number has to be 8, so the 4th can be chosen as 16, which has the greatest difference from 8, but not 12.

You got the idea. If we were to choose k numbers, if:
1) k is odd, we choose (k-1)/2 from both ends, and then choose the median.
2) k is even, we choose k/2 from both ends.

This sounds naive. But it seems to work. Complexity would be O(nlgn) for initial sorting.

Sort the sequence {a1,a2,....an-1,an}
Obviously k<=n
keep pointers at a1 and an
now .. if an - a2 > an-1 - a1 choose a2 else choose a1 (accordingly move the pointer)
keep choosing until u have k numbers

Refer problem Aggressive cows problem on spoj. Its the same problem as this one.
First we sort the array . Then we do a binary search on the answer in the range [0 maxVal-minValue+2].

Refer problem Aggressive cows problem on spoj. Its the same problem as this one.
First we sort the array . Then we do a binary search on the answer in the range [0 maxVal-minValue+2].

1. First sort the array A
2. Then solve this problem using DP as follows:
Let f(i, j) denote, maximum difference if you select i numbers from the array, starting from index j and element at index j must be selected.
f(i, j) = max { min( f(i-1, m), A[m]-A[j] ) }, m=j+1 to n-1, if i<=n-j
f(i, j) = -Infinity, if i >n-j
the goal is to solve f(1, k), (note: it is always safe to include 1st element in the k numbers), complexity is O(n^2)

DP able: O(K*n^2)
f(n,k) = Max( MIN(f(m, k-1), A[n-1]- A[m-1]), .... ) | m=1...n-1

Solved here:
geeksforgeeks.org/k-numbers-difference-maximum-minimum-k-number-minimized/

another DP problem?
I wish I had so many DP problems in my interview... sigh

binary search :)