0
$\begingroup$

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!!!.

1 Answers 1

1

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?