Voici mon code pour vous montrer mon travail. Je teste sur le compilateur de ma classe pour vous dire quelles sont mes erreurs.
// Analyse
// Question 1) a)
// Les conditions sur T sont T[i]<=T[j] et donc à fortiori on en déduit cette relation :
// LIS[i+1] = max(LIS[j])+1 avec j compris entre 1 et i.
//b)
//On va créer un algorithme qui va dire s'il existe une valeur inférieure à une valeur donnée en argument.
public class Projet{
public static boolean inferieur(int [] T, int i, int a){ // avec T la permutation, i la longeur, et a l'entier voulu
for(int j=0; j<i; j++){
if(T[j]<a){
return true;
}
else return false;
}
}
public static int[] remplir(int[] LIS, int[] T, int k){
// On va regarder si il existe une valeur inférieure à T[k] dans T :
boolean x = inferieur(T,k,T[k]);
// Il nous faut un nouveau tableau pour le LIS :
int[] NEWLIS = new int [k+1];
// Distinguons deux cas, soit il existe des valeurs inférieures à i, c'est à dire l'indice le plus à droite, donc on va chercher ces valeurs, soit il n'y en a pas, donc la plus longue sous-suite est de taille 1 :
// Premier cas :
int maximum = 0;
if(x){
for(int i=0; i<k; i++){
if((LIS[maximum]<LIS[i])&&(T[k]>T[i])){
maximum=i;
}
NEWLIS[i]=LIS[i];
}
}
// Second cas :
else{
for(int i=0; i<k; i++){
NEWLIS[k]=1;
}
}
return NEWLIS;
}
// c)
public static int[] longueur(int[] T){
int[] LIS = newint[T.length];
LIS[0]=0;
for(int i=1;i<T.length;i++){
int[] NEWLIS2 = remplir(LIS,T,i);
LIS[i] = NEWLIS2[i];
// On recherche la taille de la plus grande sous-suite
int maximum = 0;
for(int i=0; i<T.length; i++){
if(LIS[i]>maximum){
maximum = LIS[i];
}
}
return maximum;
}
}
}
)
)
)