École polytechnique
Épreuve facultative d'algorithmique

n = 10; 
tableau = Table[Random[Integer, 20], 
{n}]
a[k_] := tableau[[k + 1]]

Q1: on utilise un parcours linéaire du tableau pour déterminer le max et l'inf, la fonction est donc en temps linéaire ()

amplitude[a_] := Module[{max = -Infinity, min = 
Infinity}, 
   Do[If[a[i] > max, max = a[i]]; 
If[a[i] < min, min = a[i]], {i, 0, n - 1}]; 

    max - min]
{tableau, 
amplitude[a]}

Remarque: il est évidemment plus simple d'écrire
Max[tableau]-Min[tableau]

Q2: si le max précède le min, on aura du mal à faire un gain égal à amplitude ! Ex L'amplitude est la valeur absolue du gain ou de la perte maximale.

Q3: on utilise un parcours sur , puis sur , la fonction est donc en temps quadratique ().

gain[a_] := Module[{bid = 0}, 
Do[If[a[j] - a[i] 
> bid, bid = a[j] - a[i]], 
     {j, 
1, n - 1}, {i, 0, j}]; bid]
gain[a]

Remarque: on peut se contenter de 0≤i≤j-1.

Q4: la condition j-i minimal entraîne une difficulté. On peut noter qu'il n'y a défaut d'unicité que si le max ou l'inf est atteint plusieurs fois. Une solution est d'inverser les boucles imbriquées, de faire décrémenter et de remplacer < par ≤ !

gain[a_] := Module[{bid = 0, iMax, jMax}, 

   Do[If[a[j] - a[i] >= bid, bid = a[j] - a[i]; 

    iMax = i; jMax = j], 

     {i, 0, n - 1}, {j, n - 1, i + 1, 
-1}]; 
    {bid, {iMax, 
jMax}}]
gain[a]

Q5: pour améliorer la complexité de l'algorithme, on va garder trace des indices des valeurs optimales.

gain1[a_] := 
Module[
        {gc = 0, 
indMax = 0, indMin = 0, nveauMin = 0}, 

   Do[If[a[i] > a[indMax], gc = a[indMax = i] - 
a[indMin]]; 
      If[a[i] - 
a[nveauMin] > gc, 

            gc 
= a[indMax = i] - a[indMin = nveauMin]]; 

      If[a[i] < a[indMin], 
nveauMin = i]; , 

            {i, 
1, n - 1}]; 
gc]
            
gain1[a]

Q7 (heureusement qu'on ne demande plus un temps linéaire !)
La solution la plus lisible utilise une coupure des fonctions précédentes, en les appliquant aux deux sous-tableaux obtenus en coupant au point et en optimisant la somme des deux par itération sur .
Pour cela, on réécrit la procédure pour y faire figurer les dates extrêmes des transactions possibles.

gainCourtTerme[a_, début_, fin_] := 

  Module[{gc = début, indMax = début, 
indMin = début, nveauMin = début}, 

   Do[If[a[i] > a[indMax], gc = a[indMax = i] - 
a[indMin]]; 
      If[a[i] - 
a[nveauMin] > gc, 

            gc 
= a[indMax = i] - a[indMin = nveauMin]]; 

      If[a[i] < a[indMin], 
nveauMin = i]; , 
    {i, début + 1, 
fin - 1}]; 
    gc]

gain2[a_] := Module[{essai, top = 0}, 

   Do[essai = gainCourtTerme[a, 0, k] 

            + 
gainCourtTerme[a, k, n - 1]; 

      If[essai > top, top = 
essai], {k, 1, n - 1}]; 

            top]
            
gain2[a]

Q8: Idem en moins lisible

gct[a_, début_, fin_] := Module[{gc = 
début, indMax = début, indMin = début, 

    nveauMin = début}, 

   Do[If[a[i] > a[indMax], gc = a[indMax = i] - 
a[indMin]]; 
      If[a[i] - 
a[nveauMin] > gc, 

        gc = a[indMax = 
i] - a[indMin = nveauMin]]; 

      If[a[i] < a[indMin], 
nveauMin = i]; , 

        {i, début 
+ 1, fin - 1}]; 
    {gc, indMin, 
indMax}]
        
gain2[a_] 
:= Module[{essai, coord, bid1, bid2, top = 0}, 

   Do[essai 
=     First[bid1 = gct[a, 0, k]] + 

                First[bid2 
= gct[a, k, n - 1]]; 
      If[essai 
> top, top = essai; 

        coord = 
{bid1[[2]], bid1[[3]], bid2[[2]], bid2[[3]]}], 

                {k, 
1, n - 1}]; 

                {top, 
coord}]
                
gain2[a]

Voici une version plus idiosyncrasique où l'on adresse une liste par le numéro de ses éléments… ce qui permet de passer la liste en argument.

gct[a_List, début_, fin_] := 

Module[
    {gc = début, indMax = 
début, indMin = début, nveauMin = début}, 

   Do[If[a[[i]] > a[[indMax]], 

        gc = a[[indMax = 
i]] - a[[indMin]]]; 
      If[a[[i]] 
- a[[nveauMin]] > gc, 

        gc = a[[indMax = 
i]] - a[[indMin = nveauMin]]]; 

      If[a[[i]] < a[[indMin]], 
nveauMin = i], 
   {i, début + 1, fin}]; 

    {gc, indMin, 
indMax}]
    
gain2[a_] := 
Module[
    {essai, coord, bid1, bid2, top = 
0, n = Length[a]}, 
   Do[essai = First[bid1 = 
gct[a, 1, k]] + 

              First[bid2 
= gct[a, k, n]]; 
      If[essai 
> top, top = essai; 

             coord 
= {bid1[[2]], 
bid1[[3]],bid2[[2]],bid2[[3]]}
        ], 

    {k, 1, n - 1}]; 

    {top, 
coord}]
    
gct[{5, 12, 3, 6, 9, 14, 8, 
20, 6, 17, 10, 11}, 1, 12]