Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a vector V of n integers and an integer k, k <= n, you want a subvector (a sequence of consecutive elements of the vector ) of maximum length containing at most k distinct elements.

The technique that I use for the resolution of the problem is dynamic programming. The complexity of this algorithm must be O(n*k).

The main problem is how to count distinct elements of the vector. as you would resolve it ?

How to write the EQUATION OF RECURRENCE ?

Thanks you!!!.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Using V[i:j] to represent items i through j of the vector (not i though j-1 as in Python), I think you want to find i and j such that j-1 is maximized and the number of distinct entries is k (because if it were less than k, you could increase j or decrease i). My naive thought would be to start with i=1, j=k and make a table (kx2) with the distinct entries of V in the first column and the count in the current interval in the second. If you don't have k distinct entries, keep adding to j, updating the table, until you do. Record i and j as the best seen yet. Then increase i to 2, updating your table, and see if you can increase j. Continue through V, at each step seeing if the gap has increased. If so, replace the stored best so far i and j. I don't think this is worse than O(nk)-the original sort is k ln k, and you make only one pass through the n items. For each new item, you might have to look through k lines in the table once or twice, but it shouldn't be k^2. Does that work?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.