Looking for a dynamic programming solution
- by krammer
Given a sequence of integers in range 1 to n. Each number can appear at most once. Let there be a symbol X in the sequence which means remove the minimum element from the list. There can be an arbitrarily number of X in the sequence.
Example: 1,3,4,X,5,2,X
The output is 1,2.
We need to find the best way to perform this operation.
The solution I have been thinking is:
Scan the sequence from left to right and count number of X which takes O(n) time.
Perform partial sorting and find the k smallest elements (k = number of X) which takes O(n+klogk) time using median of medians.
Is there a better way to solve this problem using dynamic programming or any other way ?
