1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
|
/**
* @param S La liste de référence
* @param start Offset de départ dans la liste de référence
* @param subseq La SubSeq maximale en cours de remplissage
* @param subseqlen La taille actuelle de la SubSeq maximale
*/
static void findSubSeq(int[] S, int start, int[] subseq, int subseqlen) {
int min=Integer.MAX_VALUE;
for(int i=start;i<S.length;i++) {
// ignore les elements qui ne forment pas une subseq strictement croissante
if (subseqlen>0 && S[i]<=subseq[subseqlen-1]) continue;
// detection d'un element minimal
if (S[i]<min) {
min=S[i];
// empilement dans la subseq
subseq[subseqlen++]=S[i];
// traitement de la liste restante
findSubSeq(S,i+1,subseq,subseqlen);
// depilement de la subseq
subseqlen--;
}
}
// la subseq ne grossit plus -> fini : on affiche
if (min==Integer.MAX_VALUE) {
for(int i=0;i<subseqlen;i++)
System.out.print(subseq[i]+" ");
System.out.print("\n");
}
}
public static void main(String[] args) {
int[] S = new int[] {1,5,6,9,2,3,4,7,8};
long t0 = System.currentTimeMillis();
findSubSeq(S,0,new int[S.length],0);
long t1 = System.currentTimeMillis();
System.out.println("duration: "+(t1-t0)+"ms");
} |
Partager