微软面试100题(40):首尾相连的珠子

一串首尾相连的珠子（m个），有N种颜色（N《=10），设计一个算法，取出其中一段，要求包含所有N中颜色，并使长度最短。并分析时间复杂度与空间复杂度。

真是不好做唉。。和一般的DP不是很一样。做了很久了。一直不是十分能想通，最后的代码写的也很繁复，不简练。

/*
 * =====================================================================================
 *
 * Filename: bead.c
 *
 * Description:
 *
 * Version: 1.0
 * Created: 10/20/2012 11:46:48 AM
 * Revision: none
 * Compiler: gcc
 *
 * Author: [e-mail] (),
 * Organization:
 *
 * =====================================================================================
 */
#include <stdlib.h>
#include <stdio.h>

#define MAXK 10
#define    MAXM 100            /* */
int getfirstvalue(int *input,int n){
    int match = (1<<n)-1;
    int end = -1;
    int v = 0;
    do{
        end++;
        v |= 1<<input[end];
    }while(v!=match);
    return end;
}
int getnextoccur(int tarindex, int *input, int size){
    int i;
    for(i = tarindex+1;i<size*2;i++){
        if( input[i%size] == input[tarindex])
            return i%size;
    }
    return -1;
}

/*
 * === FUNCTION ======================================================================
 * Name: main
 * Description:
 * =====================================================================================
 */
    int
main ( int argc, char *argv[] )
{
    int input[] = {0,1,2,3,4,4,5,4,2,3,1,0,2,3};
    int n = 6;
    int size = sizeof(input)/sizeof(int);
    int next[size];
    int end[size];
    int i = 0;
    end[0] = getfirstvalue(input,n);
    int minlen = end[0];
    for(;i<size;i++){
        next[i] = getnextoccur(i,input,size);
    }
    for(i = 1; i<size;i++){
        end[i] = end[i-1] ;
        if( (end[i]>i && (next[i-1] < i || next[i-1]>end[i]))
            ||
            (end[i]<i && next[i-1] > end[i] && next[i-1]<i)
            ){
            end[i] = next[i-1];
        }
        printf ( "start = %d end = %d\n", i,end[i] );
        int tmp = end[i]>i?end[i]-i+1 : size-i+end[i];
        minlen = tmp>minlen?minlen:tmp;
    }
    printf ( "min length = %d\n", minlen );
    return EXIT_SUCCESS;
}                /* ---------- end of function main ---------- */