Find K Elements with Maximum Minimum Consecutive Difference

Problem: Given a sorted array A, find k elements from the array with the maximized minimum consecutive difference. For example, m1, ... , mk are selected elements. We want to maximize min(mi+1-mi). A more concrete example, a sorted array A = [1, 3, 4, 8] and k =3. There are four ways of picking 3 elements: {1,3,4}, {1, 4, 8}, {1, 3, 8}, {3, 4, 8}. The minimum consecutive difference for these four selections are 2, 3, 2, 1, respectively. The maximum of these minimum consecutive differences is 3, which is from selection {1, 4, 8}.


Solution: [*will re-edit later*] This is problem is similar to given a line, try to divide the line into several segments as even as possible. It is also similar to the "Painter and Slates" problem (see a link here). The key here is to use binary search, which will give you O(nlog(A[n-1] - A[0])). Using DP definitely is OK, but the complexity is O(k*n^2).

• Basically, the selection depends on the how "wide" the gap we use. If we use the gap as wide as A[n-1] - A[0] (n is the size of array), we can only select 2 elements. On the other way, if we choose the gap as min(A[i+1]-A[i]), we will select n elements. Our goal is to select k elements while with maximized minimum difference. k is within 2 and  n. Then a binary search can help us find k.
• We just do binary search on the space of the width of the gap. We set low =  min(A[i+1]-A[i]), high =  A[n-1] - A[0] and make mid = (low + high) /2. 
• With this mid as the width of the gap, we can calculate the number of elements we selected. If it is larger than k, we need to increase the width of the gap: we just update low = mid; Otherwise, we need to decrease the width of the gap by update high = mid.
• We stop when we find a gap such that if we further increase the gap, we can't be able to select k elements.
• Try to calculate m[i][j][k], where i and j are the index within A[] and k how many elements are selected with in the region A[i] ~ A[j]. The time to calculate this array is O(N^4).