Suite monotone (cachée dans une suite aléatoire)

Algorithmique > Suite monotone (cachée dans une suite aléatoire) [ Réagir ]

Description du problème

Soit (U_n) une suite de n termes réels, générée de façon aléatoire, ou contenant des données provenant d'une source extérieure. L'objectif est de trouver, à l'intérieur de cette suite, la suite monotone (V_m) contenant le plus de termes possibles. (Les éléments de (V_m) étant rangés dans le même ordre dans chacune des deux suites.)

Complexité en temps

Bien que la solution proposée soit bien meilleure que la solution brutale et récursive que l'on pourrait envisager en première tentative, la complexité en temps d'exécution de l'algorithme ci-dessous est tout de même en Ω(n²/2).

Adaptations

L'exemple de code qui suit renvoie le nombre de termes de (V_m), qui est construite comme une suite strictement croissante. De nombreuses adaptations peuvent être effectuées sur ce code :

• Pour chercher une suite décroissante (ou strictement décroissante, ou croissante mais pas strictement), modifier la ligne de comparaison entre deux termes.
• Pour forcer le premier terme U₀ à appartenir à (V_m), il faut rajouter les lignes de code en italique (en adaptant l'opérateur de comparaison suivant la suite souhaitée).
• Il est aussi possible de souhaiter une autre sortie que le nombre de termes de (V_m) (par exemple la suite elle-même ou bien encore les index de ses termes). Il faut alors complexifier la structure Best[] afin de stoquer pour chaque terme de (U_n) la meilleure suite possible.

Code (Pascal)

type TDoubleArray = Array of Double;

function SuiteMonotone(T: TDoubleArray; N: Integer): Integer;
var
  I,J: Integer;
  Best: TDoubleArray;
begin

  Result:=0;
  SetLength(Best,N);
  For I:= 0 to N-1 do
    begin
//    if (T[I]<T[0]) then Best[I]:=0
//    else
//      begin      
          Best[I]:=1;
          For J:= 0 to I-1 do
            if (T[J]<T[I]) then
              if (Best[J]+1)>Best[I] then Best[I]:=Best[J]+1;
          if (Best[I]>Result) then Result:=Best[I];
//      end;
    end;

end;