CODEWITHSUNDEEP
algorithmdynamic-programming
user2078217
user2078217

Reputation: 139

Dynamic Programming algorithm to delete k elements in an array

I was recently trying to solve a problem that took n sorted integers as input and we had to delete k integers from the array to maximize the minimum difference between two consecutive terms.

Example test case: ARRAY: 6,7,10,13,15 delete 2 integers.

ANSWER: Integers deleted: 7,13

My approach:

Since we have to delete k integers we iterate over the array k times. In each iteration we wind the minimum difference between two consecutive terms. Let's say that after one iteration the pair i and i+1 have minimum difference.Then we compare the difference between i-1 and i+1 and the difference between i and i+2. If the first is larger then we delete the term i else we delete i+1.

This approach is giving me a wrong answer.

Since the constraints on n and k are low ( 1<=k<=n<=30 ). I believe that the problem can be solved using dynamic programming but I do not know how to approach it.

Any help would be nice. I do not want the code just the algorithm and how it was derived. Thanks in advance

Upvotes: 1

Views: 5682

Answers (2)

kraskevich
kraskevich

Reputation: 18576

Here is a dynamic programming solution. Maybe a simpler solution exists, but this one is correct and definitely fast enough for given constraints:

1)Let's assume that f(prefix_len, last_taken, deletes_count) is the maximal difference between two consecutive numbers after processing prefix_len numbers in the array, deleting exactly deletes_count numbers and having an element with index last_index as the last remaining element so far.

2)f can be computed using the following formulas:
f(i, i, deletes_count) = max(min(f(i - 1, j, deletes_count), abs(array[i] - array[j]))) for 0 <= j < i. This formula corresponds to the case when the i-th element is not deleted.
f(i, j, deletes_count) = f(i - 1, j, deletes_count - 1). This formula corresponds to the case when the i-th element is deleted.
The base case is f(0, -1, 0) = 0(it corresponds to an empty prefix). Maybe some other corner cases should be considered(it depends on implementation details).

3)The answer is max(f(array.length, j, k)) for 0 <= j < array.length. You can find the numbers which were deleted using standard answer reconstruction techniques.

4)The time complexity is O(m^4), space complexity is O(m^3) where m = max(n, k)(it is possible to get more precise upper bound using both parameters n and k but it is not necessary).

Upvotes: 0

David Eisenstat
David Eisenstat

Reputation: 65506

Here's a fairly simple cubic-time algorithm. If we decide beforehand on a minimum difference, then a linear-time greedy algorithm tells us how many elements need to be deleted (sweep once left to right, deleting only when it's necessary given past choices). Iterate through all n choose 2 = O(n^2) possible minimum differences and take the greatest that results in at most k deletions. (To get to O(n^2 log n): sort these possible minimums and use binary search.)

Upvotes: 1

Related Questions