Shortest subsequence with no interval duplicates

Given an unsorted array of N integers and a function getNextIndexOf(int k) that returns the index of the next element whose value is 'k', how would one get at the last element (i.e., index N) with the fewest number of call开发者_StackOverflow中文版s to getNextIndexOf(int k) ?

*In other words, with what values k₁, k₂, ... , k_m should one call getNextIndexOf(int k) so that the m^th call returns 'N', and m is as small as possible?

**Edit: you can assume getNextIndexOf can keep track of the last index it returns

(e.g., like a static local variable in C). The very first call it just returns the index of the first element equal to its argument (int k).

---

Since the array is completely random and unsorted, there is a priori no reason to choose any particular number. So you cannot prefer a number over the other.

I would try a branch and bound approach. See here. Branch on the next integer to be selected as k and bound on the amount of steps already taken. Keep all branches on a priority queue and always expand the head of the queue.

This guarantees to find the optimal solution.

EDIT:

Here is some pseudo-code:

Let A be the set of all integers that occur in the array.
Let Q be the priority queue

foreach integer k in A do
  Add result of getNextIndexOf(k) to Q

while(Q is not empty && end of array not reached)
  q = head(Q)
  Dequeue(q)

  foreach(integer k in A do)
    Add result of getNextIndexOf(k) to Q (using q)

---

A possible solution (written in Java!):

public static List<Integer> getShortest(int[] array) 
{
   int[] nextChoice = new int[array.length];
   HashMap<Integer,Integer> readable = new HashMap<Integer,Integer>();

   readable.put(Integer(array[array.length-1]), Integer(array.length-1));
   for(int i = array.length-1; i>=0; i--)
   {
      for(Map.Entry<Integer,Integer> entry: readable.entrySet())
      {
         if(entry.getValue().intValue() > nextChoice[i])
            nextChoice[i] = entry.getKey();
      }
      readable.put(Integer(array[i]),i);
   }

   List<Integer> shortestList = new LinkedList<Integer>(array.length);
   for(int i = 0; i < array.length; i++)
      shortestList.add(nextChoice[i]);

   return shortestList;
}