Malgré leur prudence innée, les vaches ont perdu sur le marché hypothécaire et essaient les actions. Bessie voit l’avenir : elle connaît les prix d'aujourd'hui des $S$ $(2 \le S \le 50)$ actions et ceux de l'avenir pour $D$ jours $(2 \le D \le 10)$ au total.

Avec la matrice des prix actuels et futurs par jour $(1 \le PR_{sd} \le 1,000)$ et $M$ $(1 \le M \le 200,000)$ d'argent initial, trouvez les achats/ventes optimaux maximisant le gain lors de la vente finale. Les actions s'achètent en quantités entières ; nul besoin de tout dépenser, ni de dépenser. Le profit ne peut dépasser 500,000.

Exemple d'un marché haussier, favori de Bessie : $S=2$, $D=3$, argent 10. Colonnes : prix aujourd'hui, demain, après-demain.

                   Today's price
                   |   Tomorrow's price
                   |   |  Two days hence
             Stock |   |  | 
              1    10 15 15
              2    13 11 20

Pour gagner, achat de l’action 1 au jour 1. Vente au jour 2 puis achat immédiat de l’action 2 : 4 en banque et une action 2. Vente finale à 20, ajoutée à la banque : total 24.

Entrée

• Ligne 1 : entiers espacés $S$, $D$, $M$.
• Lignes $2,\ldots,S+1$ : ligne $s+1$, $D$ prix $PR_{sd}$ de l'action $s$ aux jours $1,\ldots,D$.

Sortie

• Ligne 1 : argent maximal après vente au jour $D$.

Exemples

Entrée 1

2 3 10
10 15 15
13 11 20

Sortie 1

24

Auteur : Rob Kolstad(?), 2008