{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["# 1A.algo - La sous-s\u00e9quence de plus grande somme\n", "\n", "Ce probl\u00e8me est connu sur le nom de [Maximum subarray problem](http://en.wikipedia.org/wiki/Maximum_subarray_problem). Notion abord\u00e9e : programmation dynamique."]}, {"cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": ["%matplotlib inline"]}, {"cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [{"data": {"text/html": ["
run previous cell, wait for 2 seconds
\n", ""], "text/plain": [""]}, "execution_count": 3, "metadata": {}, "output_type": "execute_result"}], "source": ["from jyquickhelper import add_notebook_menu\n", "add_notebook_menu()"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Enonc\u00e9\n", "\n", "On suppose qu'on a une liste $L=( l_1, l_2, ..., l_n)$. On souhaite trouver la sous-s\u00e9quence de plus grande somme. En d'autres termes, on veut trouver $(i^*,j^*)$ tels que :\n", "\n", "$\\sum_{k=i^*}^{j^*} l_k = \\max_{i,j} \\sum_{k=i}^{j} l_k$"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Solution na\u00efve\n", "\n", "La premi\u00e8re solution consiste \u00e0 calculer les sommes de toutes les sous-s\u00e9quences et de garder les $i,j$ qui ont permis d'obtenir la meilleure sous-s\u00e9quence. On divise le programme en deux fonctions :\n", "\n", "* ``somme_partielle`` : calcule la somme de la sous-s\u00e9quence ``l[i:j]`` (co\u00fbt de la fonction : $O(n)$)\n", "* ``plus_grande_sous_liste`` : passe en revue toutes les sous-s\u00e9quences et retourne la meilleure (co\u00fbt de la fonction $O(n^2)$)\n", "\n", "Le co\u00fbt de cet algorithme est en $O(n^3)$."]}, {"cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [{"data": {"text/plain": ["[7, -1, 8]"]}, "execution_count": 4, "metadata": {}, "output_type": "execute_result"}], "source": ["def somme_partielle(li, i, j):\n", " r = 0\n", " for a in range (i, j) :\n", " r += li[a]\n", " return r\n", " # on pourrait juste \u00e9crire \n", " # return sum(li[i:j])\n", "\n", "def plus_grande_sous_liste(li):\n", " meilleur = min(li) # ligne A\n", " im, jm = -1, -1\n", " for i in range(0, len(li)):\n", " for j in range(i+1, len(li)+1): # ne pas oublier +1 car sinon\n", " # le dernier \u00e9l\u00e9ment n'est jamais pris en compte\n", " s = somme_partielle(li, i, j)\n", " if s > meilleur:\n", " meilleur = s\n", " im, jm = i, j\n", " return li [im:jm]\n", " \n", "# si li ne contient que des valeurs positives, la solution est \u00e9videmment la liste enti\u00e8re\n", "# c'est pourquoi il faut tester cette fonction avec des valeurs n\u00e9gatives\n", "li = [ 4,-6,7,-1,8,-50,3]\n", "m = plus_grande_sous_liste(li)\n", "m"]}, {"cell_type": "markdown", "metadata": {}, "source": ["La ligne A contient l'instruction ``meilleur = min(li)``. Pour une liste o\u00f9 tous les nombres sont n\u00e9gatifs, la meilleure sous-liste est constitu\u00e9 du plus petit \u00e9l\u00e9ment de la liste. Remplacer cette instruction par ``meilleur = 0`` a pour cons\u00e9quence de retourner une liste vide dans ce cas pr\u00e9cis. \n", "\n", "$cout(n) = \\sum_{i=0}^n \\sum_{j=i+1}^n j-i = \\sum_{i=0}^n \\sum_{j=0}^i j = \\sum_{i=0}^n \\frac{i(i+1)}{2} \\sim O(n^3)$"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Solution plus rapide\n", "\n", "Il est possible de modifier cette fonction de telle sorte que le co\u00fbt soit en $O(n^2)$ car on \u00e9vite la r\u00e9p\u00e9tition de certains calculs lors du calcul de la somme des sous-s\u00e9quences. On peut \u00e9crire :\n", "\n", "$\\sum_{k=i}^{j+1} l_k = l_j + \\sum_{k=i}^{j} l_k$\n", "\n", "Dans la seconde boucle, il suffit d'ajouter l'\u00e9l\u00e9ment ``li[j]`` \u00e0 la somme pr\u00e9c\u00e9dente."]}, {"cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["[7, -1, 8]\n", "[78, 9, 7, 7]\n"]}, {"data": {"text/plain": ["[7, -1, 8]"]}, "execution_count": 5, "metadata": {}, "output_type": "execute_result"}], "source": ["def plus_grande_sous_liste_n2(li):\n", " meilleur = 0\n", " im, jm = -1, -1\n", " for i in range (0, len(li)):\n", " s = 0\n", " for j in range(i, len(li)):\n", " s += li[j]\n", " if s > meilleur:\n", " meilleur = s\n", " im, jm = i, j+1\n", " return li[im:jm]\n", " \n", "li = [ 4, -6, 7, -1, 8, -50, 3]\n", "m = plus_grande_sous_liste_n2(li)\n", "print(m)\n", "\n", "li = [1, 2, 3, 4, 5, -98, 78, 9, 7, 7]\n", "m = plus_grande_sous_liste_n2(li)\n", "print(m)\n", "\n", "li = [0, 2, 4, -7, -2, 7, -1, 8, -10, 3]\n", "m = plus_grande_sous_liste_n2(li)\n", "m"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Solution dichotomique\n", "\n", "Il existe une derni\u00e8re version plus rapide encore. Si on consid\u00e8re la liste $L=(l_1, ..., l_n)$ dont on cherche \u00e0 extraire la sous-s\u00e9quence de somme maximale. Supposons que $l_a$ appartienne \u00e0 cette sous-s\u00e9quence. On construit la fonction suivante :\n", "\n", "$f(a,k) =\\left \\{ \\begin{array}{ll} \\sum_{i=a}^{k} l_i &si \\; k > a \\\\ \\sum_{i=k}^{a} l_i &si \\; k < a \\end{array} \\right .$\n", "\n", "On cherche alors les valeurs $k_1$ et $k_2$ telles que :\n", "\n", "$\\begin{array}{rcl} f(a,k_1) &=& \\max_{ka} f(a,k) \\end{array}$\n", "\n", "La sous-s\u00e9quence de somme maximale cherch\u00e9e est $[k_1,k_2]$ avec $a$ dans cet intervalle et le co\u00fbt de cette recherche est en $O(n)$. Mais ceci n'est vrai que si on sait que $l_a$ appartient \u00e0 la sous-s\u00e9quence de somme maximale.\n", "\n", "Autre consid\u00e9ration : pour deux listes $l_1$ et $l_2$, la s\u00e9quence maximale de la r\u00e9union des deux appartient soit \u00e0 l'une, soit \u00e0 l'autre, soit elle inclut le point de jonction.\n", "\n", "Ces deux id\u00e9es mises bout \u00e0 bout donne l'algorithme suivant construit de fa\u00e7on r\u00e9cursive. On coupe la liste en deux parties de longueur \u00e9gale :\n", "\n", "* On calcule la meilleure s\u00e9quence sur la premi\u00e8re sous-s\u00e9quence.\n", "* On calcule la meilleure s\u00e9quence sur la seconde sous-s\u00e9quence.\n", "* On calcule la meilleure s\u00e9quence en suppose que l'\u00e9l\u00e9ment du milieu appartient \u00e0 cette s\u00e9quence.\n", "\n", "La meilleure s\u00e9quence est n\u00e9cessairement l'une des trois."]}, {"cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["[7, -1, 8]\n", "[78, 9, 7, 7]\n"]}, {"data": {"text/plain": ["[7, -1, 8]"]}, "execution_count": 6, "metadata": {}, "output_type": "execute_result"}], "source": ["def plus_grande_sous_liste_nlnn2_r(li, i, j):\n", " if i == j:\n", " return 0\n", " elif i+1 == j:\n", " return li[i], i, i+1\n", " \n", " milieu = (i+j) // 2\n", " \n", " # on coupe le probl\u00e8me deux\n", " ma, ia, ja = plus_grande_sous_liste_nlnn2_r(li, i, milieu)\n", " mb, ib, jb = plus_grande_sous_liste_nlnn2_r(li, milieu, j)\n", " \n", " # pour aller encore plus vite dans un cas pr\u00e9cis\n", " if ja == ib:\n", " total = ma + mb\n", " im, jm = ia, jb\n", " else :\n", " # on \u00e9tudie la jonction\n", " im, jm = milieu, milieu+1\n", " meilleur = li[milieu]\n", " s = meilleur\n", " for k in range(milieu+1, j):\n", " s += li[k]\n", " if s > meilleur:\n", " meilleur = s\n", " jm = k + 1\n", " \n", " total = meilleur\n", " meilleur = li[milieu]\n", " s = meilleur\n", " for k in range(milieu-1, i-1, -1):\n", " s += li[k]\n", " if s > meilleur:\n", " meilleur = s\n", " im = k\n", " \n", " total += meilleur - li[milieu]\n", " \n", " if ma >= max(mb,total):\n", " return ma, ia, ja\n", " elif mb >= max(ma,total): \n", " return mb, ib, jb\n", " else:\n", " return total, im, jm\n", " \n", "def plus_grande_sous_liste_nlnn2(li):\n", " m, i, j = plus_grande_sous_liste_nlnn2_r(li, 0, len(li))\n", " return li[i:j]\n", " \n", "li = [ 4, -6, 7, -1, 8, -50, 3]\n", "m = plus_grande_sous_liste_nlnn2(li)\n", "print(m)\n", "\n", "li = [1, 2, 3, 4, 5, -98, 78, 9, 7, 7]\n", "m = plus_grande_sous_liste_nlnn2(li)\n", "print(m)\n", "\n", "li = [0, 2, 4, -7, -2, 7, -1, 8, -10, 3]\n", "m = plus_grande_sous_liste_nlnn2(li)\n", "m"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Le co\u00fbt de cette fonction est au pire en $O(n \\ln n)$. A chaque it\u00e9ration, on effectue trois calculs :\n", "\n", "* meilleure s\u00e9quence \u00e0 droite : $f(n/2)$\n", "* meilleure s\u00e9quence \u00e0 gauche : $f(n/2)$\n", "* meilleure s\u00e9quence incluant $a$ : $n$\n", "\n", "Le co\u00fbt de l'iteration $n$ est $f(n)=n + 2f(n/2)$ avec $f(1)=0$. On calcule les premi\u00e8res termes : "]}, {"cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["f(2)=2 --> f(2)/2 = 1.0\n", "f(4)=8 --> f(4)/4 = 2.0\n", "f(8)=24 --> f(8)/8 = 3.0\n", "f(16)=64 --> f(16)/16 = 4.0\n", "f(32)=160 --> f(32)/32 = 5.0\n", "f(64)=384 --> f(64)/64 = 6.0\n", "f(128)=896 --> f(128)/128 = 7.0\n", "f(256)=2048 --> f(256)/256 = 8.0\n", "f(512)=4608 --> f(512)/512 = 9.0\n"]}], "source": ["cout = lambda n: 0 if n == 1 else n + 2 * cout(n//2)\n", "for i in range(1, 10):\n", " print(\"f({0})={1} --> f({0})/{0} = {2}\".format(2**i, cout(2**i), cout(2**i) / 2**i))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["On suppose que $f(2^n)=n2^n \\Leftrightarrow f(n) = n \\ln_2 n$. Il suffit de v\u00e9rifier cela avec la r\u00e9currence : \n", "\n", "$\\begin{array}{rcl} f(n) &=& n + 2f(\\frac{n}{2}) = n + 2 \\frac{n}{2} \\ln_2(\\frac{n}{2}) \\\\ &=& n + n \\ln_2(n) - n\\ln_2(2) = n + n\\ln_2(n) - n = n\\ln_2 n\\end{array}$\n", "\n", "C'est le co\u00fbt d'une it\u00e9ration. Comme \u00e0 chaque it\u00e9ration on coupe le probl\u00e8me en deux, le co\u00fbt total de l'algorithme est :\n", "\n", "$\\begin{array}{rcl} C(2^n) &=& f(2^n) + 2f(2^{n-1}) + 4f(2^{n-2}) + ... + 2^{n-1}f(2) = \\sum_{k=1}^{n} 2^{n-k} f(2^k) \\\\ &=& \\sum_{k=1}^n 2^{n-k} 2^k k = \\sum_{k=1}^n 2^n k = 2^{n-1}n(n-1) \\leqslant 2^{n-1} n^2 \\end{array}$\n", "\n", "Par cons\u00e9quent, le co\u00fbt est en $C(n) \\sim O(n \\ln^2 n)$."]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Solution lin\u00e9aire\n", "\n", "La derni\u00e8re solution est la plus rapide. Elle consiste \u00e0 parcourir la liste dans le sens croissant des indices et \u00e0 construire la s\u00e9rie cumul\u00e9e."]}, {"cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [{"data": {"image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAEICAYAAABcVE8dAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAgAElEQVR4nO3dd1xUZ9r/8c81VBWsgA3FhmBvqKiJihpNT8ymR9OTzW72yWazm83uk2fz7LO7+W3LbupumjExlphq2qaYRI3RiIoFS+wFxAaKiqL0+/fHGQwamGFgmDPler9evICZc+ZcoFwc7nOf7y3GGJRSSgU/h90FKKWU8g1t+EopFSK04SulVIjQhq+UUiFCG75SSoUIbfhKKRUitOErFaBExIhIr1oe/7eI/MmOmpR/04avVBARkXuBUmPM/9hdi/I/ojdeKRWYRMQAycaYnXbXogKDnuErnxORR0Rkv4icFJFtIjLR+XiUiDwlIgecb0+JSJTzufEikicivxaRfBE5KCJXi8ilIrJdRApF5L9rHOP3IvK2iMxxHmejiPQWkd86998nIpNrbN9KRF5xvu5+EfmTiITVUX+YiPy3iOxyvvYaEekiIt2cwyzhNbZdIiJ3Oz++XUSWi8iTInJcRHaLyGjn4/ucdd1W27419l9WR01RIvKEiOSKyGEReUFEmtV4/nIRWe887rciMrAh/3YqsGnDVz4lIinAz4DhxphYYAqw1/n0o0A6MBgYBIwAag5NdACigc7AY8DLwDRgGHAh8JiI9Kix/RXAbKANsA74HOv/fGfgD8CLNbadBVQAvYAhwGTgbmr3EHATcCnQErgTOF3Pb8FIYAPQDpgHzAeGO487DXhORGLq+Vo1/RXojfW968X33yNEZCgwE/ix87gvAh9W/zJVIcQYo2/65rM3rGaUD0wCIs57bhdwaY3PpwB7nR+PB84AYc7PYwEDjKyx/RrgaufHvwe+qPHcFcCpWvZvDbQHSoFmNba/CVhcx9ewDbiqlse7OV8zvMZjS4C7nR/fDuyo8dwA5/btazx2FBh8/r419l9W43Pj/H4KUAz0rPHcKGCP8+PngT/W8jWMs/v/g7759u3sn55K+YIxZqeIPIjVkPuJyOfAQ8aYA0AnIKfG5jnOx6odNcZUOj8+43x/uMbzZ4CaZ8fnP3eklv1jnMeIAA6KSPX2DmBfHV9GF6xfTg1xfk0YY1x9DfURDzQH1tSoX4DqIakk4DYR+a8a+0Ry7vdWhQAd0lE+Z4yZZ4y5AKsRGazhCIADzseqdXU+1tT2YZ3hxxljWjvfWhpj+rnYvmctjxc73zev8ViHRtRVXM/XOoL1i6JfjfpbGWOqf3HsAx6v8VxrY0xzY8wbjahNBSBt+MqnRCRFRCY4x49LsBpV9Vn3G8D/iEi8iMRhjUHPaeqajDEHgYXAP0SkpYg4RKSniIyrY5cZwB9FJFksA0WknTGmANgPTHNe2L2T2n8x1Nd64BoRae6cb39XHfVXYV3PeFJEEgBEpLOITHFu8jJwn4iMdNbbQkQuE5HYRtSmApA2fOVrUcBfsM5KDwEJQPXsmj8BWVgXNTcCa52P+cKtWMMc3wHHgHeAjnVs+0/gLaxfEkXAK0D1jJh7gIexxuL7Ad82oqYngTKsYaBZwFwX2z4C7AQyRaQI+BJIATDGZDnreg7ra9uJdT1AhRidh6+UUiFCz/CVUipEaMNXSqkQoQ1fKaVChDZ8pZQKEX5941VcXJzp1q2b3WUopVTAWLNmzRFjTHxtz/l1w+/WrRtZWVl2l6GUUgFDRHLqek6HdJRSKkRow1dKqRChDV8ppUKEX4/h16a8vJy8vDxKSkrsLsUvRUdHk5iYSEREhN2lKKX8TMA1/Ly8PGJjY+nWrRs1omAV1toGR48eJS8vj+7du9tdjlLKzwTckE5JSQnt2rXTZl8LEaFdu3b6149SqlYB1/ABbfYu6PdGKVWXgGz4SqkgUlEGWTOhotTuSoKeNnw/tnfvXvr37293GUo1rY1vw8e/sN6rJqUNXyllrw3zrfc7FtpbRwjQht8Ar7/+OgMHDmTQoEFMnz6d22+/nXfeeefs8zEx1lKiS5YsYdy4cVx//fX07t2b3/zmN8ydO5cRI0YwYMAAdu2y1sGua3+lgt6J/bDnGwiPhl2LobLc7oqCWsBNy6zp/z7azHcHirz6mn07teR/r6hr7WrYvHkzjz/+OMuXLycuLo7CwkIeeuihOrfPzs5my5YttG3blh49enD33XezatUqnn76aZ599lmeeuopr9avVEDZ+BZgIONR+OJ3kJsJ3S+0u6qgpWf4Hlq0aBHXXnstcXFxALRt29bl9sOHD6djx45ERUXRs2dPJk+eDMCAAQPYu3dvU5erlP8yBrLfhC4jIe0OcETosE4TC+gzfFdn4k3FGPODqY/h4eFUVVWdfb6srOzsc1FRUWc/djgcZz93OBxUVFS43V+poHVoAxRsgcv+CVGxkDTaaviT/2h3ZUFLz/A9NHHiRN566y2OHj0KQGFhId26dWPNmjUAfPDBB5SXezYO2dj9lQpI2W9CWCT0m2p9njwZCrbCsTrTfVUjacP3UL9+/Xj00UcZN24cgwYN4qGHHuKee+7h66+/ZsSIEaxcuZIWLVp49JqN3V+pgFNZYU3DTJ4MzZ3Dor2nWO91WKfJiDHG7hrqlJaWZs5fAGXLli306dPHpooCg36PlN/b8SXM/RHcMAf6XGE9Zgw8MxjiUuCWt+ytL4CJyBpjTFptz+kZvlLK9zbMh+jW1hl+NRFIngJ7lkL5GftqC2La8JVSvlV6ErZ8DP2vgfCoc59LngwVZ2DvMntqC3La8JVSvrXlI6upD7zxh891uwDCm+k4fhPRhq+U8q3s+dCmO3QZ8cPnIqKhxzjY/rk1pq+8Shu+Usp3Tuy3xugH3mCN2dcmeTIcz4EjO3xbWwjQhq+U8p3qKIWB19e9TfWF3B2f+6SkUFLvhi8iM0UkX0Q21Xjs7yKyVUQ2iMgCEWldx757RWSjiKwXkazatlE/VDMe+YsvvmDYsGEMGDCAYcOGsWjRIpurU8pD1VEKiSOgXc+6t2vdBRL66jh+E/DkDP814OLzHvsC6G+MGQhsB37rYv8MY8zguuaHKtfi4uL46KOP2LhxI7NmzWL69Ol2l6SUZ6qjFAbd4H7b5Isg51so8W44Yqird8M3xiwFCs97bKExpsL5aSaQ6MXa/JYd8chDhgyhU6dOgHW3b0lJCaWlukKQCiDZb1oBaf2ucb9t8mSoqoDdS5q8rFDizfC0O4E363jOAAtFxAAvGmNequtFRORe4F6Arl27uj7ip7+BQxsbVGydOgyAS/5S59P+EI/87rvvMmTIkHOC2ZTya9VRCr2nfB+l4EqXkRDVyhrW6Xtl09cXIrxy0VZEHgUqgLl1bDLGGDMUuAS4X0TG1vVaxpiXjDFpxpi0+Ph4b5TnVXbHI2/evJlHHnmEF1980eN9lbLN7iVQnA+Dapl7X5uwCOiZATu+0OmZXtToM3wRuQ24HJho6gjmMcYccL7PF5EFwAhgaWOP7epMvKnYGY+cl5fH1KlTef311+nZ08VFL6X8TW1RCu70ngLfvW+N/Xcc1HS1hZBGneGLyMXAI8CVxpjTdWzTQkRiqz8GJgObats2ENgVj3z8+HEuu+wy/vznPzNmzJhGfhVK+ZCrKAVXek2y3m/X2Tre4sm0zDeAFUCKiOSJyF3Ac0As8IVzyuULzm07icgnzl3bA8tEJBtYBfzHGPOZV78KH7IrHvm5555j586d/PGPf2Tw4MEMHjyY/Px8b31ZSjUdV1EKrsQkQKehOj3TizQeOQjp90j5lVlXwvFceGBd3XfX1mXxn+Hrv8LDu6BFu6apL8hoPLJSyh71iVJwpfdkwMCur7xeWijShq+Uajob38ZtlIIrHYdA8zgrTE01WkA2fH8ehrKbfm+U3zAGNtQjSsEVh8O663bnl1BV6d36QlDANfzo6GiOHj2qja0WxhiOHj1KdHS03aUoZd0Umf9d/aIUXEmeDCXHIW+1d+oKYd6809YnEhMTycvLo6CgwO5S/FJ0dDSJiSGRcKH8Xfb8+kcpuNJzAkiYNVuna7p3agtRAdfwIyIi6N69u91lKKVc8TRKwZVmra1Gv2MhTHzMO/WFqIAb0lFKBYDqKIWBjRzOqZZ8kTVEVHTAO68XorThK6W8rzpKofcU77xesvN1dnzhndcLUdrwlVLe1dAoBVcS+kDLRL3rtpG04SulvKuhUQquiFg3Ye1eAhW6DkRDacNXSnlX9nxo0x26jKjX5sWlFTzx+TaKStyEDiZPhrJT1kpYqkG04SulvKcBUQrvrc3jucU7+WC9mwuy3cdCWJSO4zeCNnyllPc0IErh3bX7AVi81U36a2QL6HYB7NCYhYbShq+U8o4GRCnsLjjF+n3HaRkdzre7jlBS7iY+IXkyHN0JR3d5oeDQow1fKeUdDYhSeH/dfkTg0cv6UFJeRebuo653SL7Ieq/DOg2iDV8p5R0b3vQoSsEYw4L1+7mgVxxXDe5MdITD/bBOu57QrpdOz2wgbfhKqcZrQJRCVs4x9hWeYeqQzkRHhDGmZxyLtxW4D0ZMngJ7l0FZsRcKDy3a8JVSjbdnCZw67FGUwntr99MsIowp/ToAMD41gdzC0+wqcNPIky+CylJrNpDyiDZ8pVTjZXsWpVBSXsl/Nhzg4v4daBFlZThmpMQDsGSbm2GdpNEQGaPDOg2gDV8p1TjVUQr9ptY7SmHx1nyKSiqYOqTz2ccS2zSnd/sYFrkbxw+Pgh7jYftCa2aQqjePGr6IzBSRfBHZVOOxtiLyhYjscL5vU8e+tzm32SEitzW2cKWUn6iOUhhU/yiF99btJyE2ijG94s55PCM1gdV7CzlZn7tui/Igf0tDKg5Znp7hvwZcfN5jvwG+MsYkA185Pz+HiLQF/hcYCYwA/reuXwxKqQCTPR/adIMuI+u1+bHiMpZsy+eqwZ0Ic5x7N25GSgLllYblO4+4fpGz0zP1JixPeNTwjTFLgcLzHr4KmOX8eBZwdS27TgG+MMYUGmOOAV/ww18cSqlAczZK4cZ6Ryl8vOEA5ZWGqUN+uDLbsKQ2xEaHs3irmxXtWnaCDgN0Pr6HvDGG394YcxDA+T6hlm06A/tqfJ7nfOwHROReEckSkSxdxlApP9eAKIX31u0ntUMsfTu1/MFzEWEOxibHs3hbfj2mZ06G3Ew4c8zDokOXry7a1varv9Z/TWPMS8aYNGNMWnx8fBOXpZRqsAZEKew5Usy63OPnXKw93/iUePJPlrL5QJHrF0ueDKYSdi32pOqQ5o2Gf1hEOgI439d2iT0P6FLj80RA1ypTKpA1IEphgTNK4arBrhq+NUjgdnpm4nBo1kanZ3rAGw3/Q6B61s1twAe1bPM5MFlE2jgv1k52PqaUClQNiVJYl8eYnnF0aBVd53bxsVEMTGzlfnqmIwx6TrTG8auqPKk8ZHk6LfMNYAWQIiJ5InIX8BfgIhHZAVzk/BwRSRORGQDGmELgj8Bq59sfnI8ppQJRI6MU3MlISWDdvuMUFpe53rD3FDh9BA6uq1cNoc7TWTo3GWM6GmMijDGJxphXjDFHjTETjTHJzveFzm2zjDF319h3pjGml/PtVW9/IUopH2pElMLF/Tu43TYjNQFjYOl2NxM3ek4ExLoJS7mld9oqpTyX/WajoxRcGdi5Fe1aRLLY3Th+i3bWWL6O49eLNnyllGdKT8HWxkcpuOJwCONS4vl6ewGVVfWYnnlgLZxy88tBacNXSnloy0dQftorUQquZKQkcPx0Oev3uZln33uy9X7nl/V+7VClDV8p5ZnsN7wWpeDK2OR4whzifrZOh4EQ0wG268Q/d7ThK6Xq72yUwg1eiVJwpVXzCIZ1beM+ZkEEkidZN2BVugldC3Ha8JVS9Xc2SsGD2TkuohTcyUhN4LuDRRw6UeJ6w+QpUHoC9q30+BihRBu+Uqp+zkYpDPdqlIIrGan1XBSlx3jrJjCdreOSNnylVP2cjVKo/8Xa+kQpuJLSPpZOraLdT8+MbglJo3Q+vhva8JVS9dOAKIX31+13G6XgiogwPjWBZTuOUFpR6Xrj5MlQsAWO5zboWKFAG75Syr0GRCmsyTlGbuHpBg/nVJuQkkBxWSVZe91Mz0x23gSmGfl10oavlHKvIVEK6+ofpeDK6F7tiAx3uJ+eGZcMrZN0HN8FbfhKKfcaEKXwcfYBpvRrX68oBVeaR4aT3qOd+3F8Eau+3V9DuZtZPSFKG75SyrXGRCkM9WzufV0yUuLZXVBMztFi1xsmT7YWVN+7zCvHDTba8JVSrjUwSiE+NooxPdt5pYQM56Ioi90N63S7AMKb6bBOHbThK6Vc2zC/YVEKgzoRHuadFtMtrgU94lqwaJubu24jmkH3sbDjc+u+AXUObfhKqboVHbDGxBsQpXCNl4Zzqo1PSSBz91FOl1W43jD5Iji2F47u9Orxg4E2fKVU3XwcpeDKhNQEyiqqWLHrqOsNk53pmRqm9gPa8JVStTMGsuf7NErBleHd29A8Msz99Mw2SRCfquP4tdCGr5SqXXWUggdn942NUnAlKjyMC3rFsWRbAcbd+HzyZMj5FkpPer2OQKYNXylVu+oohf4/qtfm3ohScCcjNYH9x8+w/fAp1xsmT4aqcti9pEnqCFSNbvgikiIi62u8FYnIg+dtM15ETtTY5rHGHlcp1YSqoxSSJ/s8SsGVs9Mz3d2E1TUdolrqsM55GncLHGCM2QYMBhCRMGA/sKCWTb8xxlze2OMppXygOkrBw7n33ohScKVDq2j6dGzJoq353DfOxXWFsAjomWHl6hhT7xlGwc7bQzoTgV3GmBwvv65Sypc8jFIorajkPxsOeiVKwZ0JqfGsyTnGiTNuVrdKngInD1rXIhTg/YZ/I/BGHc+NEpFsEflURPrV9QIicq+IZIlIVkGBm5sslFLe18AohRNnyr0WpeBKRkoClVWGb3a46Q+9Jlnvd+j0zGpea/giEglcCbxdy9NrgSRjzCDgWeD9ul7HGPOSMSbNGJMWHx/vrfKUUvXVkCiFtd6NUnBlcJfWtGoW4X6t29j20GmIxiXX4M0z/EuAtcaYw+c/YYwpMsaccn78CRAhInFePLZSylsaEKWw2MtRCq6EhzkY1zuer7fnU1VVj+mZeavhdGGT1xUIvPmvcxN1DOeISAcR66qJiIxwHtfN7XJKKZ9rRJTC1KFNNzvnfBmp8Rw5VcbG/Sdcb5g8GUwV7PzKN4X5Oa80fBFpDlwEvFfjsftE5D7np9cCm0QkG3gGuNG4vXNCqSBWUQqVbi462qGBUQop7WPp29G7UQqujOudgEg9pmd2GgrN4wJrHL/sNBzd1SQv7ZWGb4w5bYxpZ4w5UeOxF4wxLzg/fs4Y088YM8gYk26M+dYbx1UqIFVVwYtj4Ylk+PAB64y6ys16rb6S/WbDohSGdkZ8OPWxbYtIBndp7T4u2eGwLt7u/NJ/vseulJfA/Jvh1Uua5C5hvdNWKV/b+SUUbIWEvrDxHXj9SvhnH/jk15C70vqFYIdDGyF/c4OiFK5ugigFdyakJJCdd4KCk6WuN+w9Gc4cg/1rfFNYQ1WUwVu3wu7FMOn3EBXr9UNow1fK11bPgJj2MP19eHgnXPcadBkBa16DmZPh6YGw8HdwYL1vM92z5/tdlIIrGanWXbdfb3czW6fnBJAw/07PrCyHd+6whp4ufwoG39wkh9GGr5QvHdtr3e4/7HYIj4TI5tZ89xvmWM1/6ouQ0Acy/w0vjYNnh8GixyF/a9PW5adRCq7069SShNgo9+P4zdpYM478NWahqhLeu9e69+Hiv0LaHU12KG34SvlS1kwQBwy97YfPRbe05r7f8jb8agdc8TS06gxL/w7/HgnPj4Fv/gGFe7xf19koBc8u1jZ1lIIrIsL4lHiWbi+gvNLNMFjyRXBoAxQd9E1x9VVVBR/cD5vfg4v+AOn3ud+nEbThK+Ur5SWwdjakXmo1cleat7X+CrjtI/jlVrjkbxDZAr76AzwzGF7KgG+fgxP7vVNb9psQ3Qp6X1yvzX0ZpeBKRkoCJ0sqWJtzzPWG1RERO/3oJixj4OMHIfsNyHgUxvy8yQ+pDV8pX9m8AM4UwvB7PNsvtgOM/DHctRAe3GidCZpKWPgoPNkXZl5iXRc41cAoEj+PUnDlguQ4wh3CInfDOgl9oWVn/xnHNwY+fQTWzoILfwljH/bJYbXhK+Urq2dAXG9rke2Gat3VOhP88VL42RrrzPD0UfjPL+EfKTB7KqybA2eO1/81z0Yp3FTvXXwZpeBKbHQEw7u1ZYm7mAURa1hn9xJrNoydjIEvfgerXoRRP4MJv/NZmqc2fKV84cA62J8Fw+/23g93XC8Y92u4fyX85Fu44EEo3G2NCf+9F7xxE2x42zqDd8XPoxTcmZCawLbDJ9l//IzrDZOnQNkpyLX5NqDFj8O3z1p/6U3+k0+jm+3/11IqFKyeARHNPQokqzcRaN8PJj4GD6yHexZZQ0AH1sN7d1vN/+3bnWfyJefu25AohY0HfR6l4EpGqhWy6PYmrO5jISzS3jC1r/9uXYQfeqt1XcbHOf3a8JVqameOWTdYDbzeujDalESg8zCY8jj8YjPc8SkMuQX2fANvTrOa/4L7rKZXWd6gKIUFa/N8HqXgSs/4GLq0bcYSd+P4UTHQ7QL7xvGXPwOL/wQDb7Tm2jt833614Qe5U0XHWPPJDCorKuwuJXStnwcVJdZwji85HJA0Gi77B/xyG0xfAP2ugq2fwNxrrWiH5c94HKWw1oYoBVdEhIyUBJbvPEpJuZv4hOTJcHSHNfTlSytfssbt+02Fq/4FjjDfHt9JG34QM1VVbH/xVoat+iUbP33R7nJCU1WVNZzTJR06DLCvjrBw647Tq/4FD++Am+ZbGTNV5TDi3nq/THWUwlWDOzVhsZ7LSE3gTHklK/e4iUFOnmy93/Fl0xdVbc1r8OnDkHo5XPOy9W9hE234QWz1e08xtHgpxSaKhPX/CozwqGCze7F1Nunrs3tXwqMg5RL40Qz4Ta411FQP1VEKo3u2o2OrZk1cpGdG9WhHdITD/Th+u57Qtqfv0jPXz4OPHrR+0Vw701pr10ba8INUzpY1DNj4ZzZGDWVZvz/QqXI/B5bPs7us0LN6BrSIh75X2l1Jo30fpWDv3PvaREeEMbpnHIu25uM2eb33FOuaRtnppi1q4zvWjKke4+D62fW+x6EpacMPQiWnT1H19p2ckWg63jGL4Zfezg6TSNjyf9iXxBiKjufC9s+sGRl+8MPeWHZHKbiTkRJPbuFpdh8pdr1h8kVQWQp7ljZdMVs+svJxuo6CG+dBhO/D5WqjDT8IZc/8L7pX7WXfuH8S16ErbWOiWZl4B+1L9nBm44d2lxc61rxmvR/WdGFYvlIzSiHGxigFV8anWOmZbod1ksZARIumC1Pb/jm8fQd0Hgo3v2lFYvgJbfhBZt3COYw88h6Z7W9iUMZ1Zx/vP/l29lS15/RXf/Ft5G6oqiiFNbOg9yXQuovd1TSav0QpuNKlbXOSE2Lcp2eGR0GP8VbD9/bPwq5F8OZ0676IW95pkkz7xtCGH0QO5+2i+7ePsDOsJ0Pu+Oc5zw3q2o4PY2+kXdEWjJ03noSK7z6E00dg+F12V+IV/hKl4E5GagKr9hRyqtTNNOTki+DEPmshGm/ZuwzeuBnikq0psM1ae++1vUQbfpCorKjgyOu3EWnKibzxNaKim5/zvIjQedzt5Jk4Tn3xZz3Lb2qrZ1izQXpk2F1Jo/lblIIrGSkJlFcalu044nrD6umZ3roJK3clzL0e2iTBrR/Ue00BX/Pvfz1Vb6tmP0q/so1sHvK/dE0eWOs2lw1OYpZcTWzBWtj7jY8rDCGHNsK+TOvs3oa7Kb3N36IUXEnr1obYqHD3d9226gzt+3snZmH/GutGttgOVrNvEdf412wiXvvfKCJ7RWSjiKwXkaxanhcReUZEdorIBhEZ6q1jh7qtKxcyfO9LZLWcRNqVP6lzu2aRYTiGTiPftKZs0V99WGGIWT0Dwps12TJ1vuZvUQquRIQ5uLB3HIu31WN6ZvJkyF3hWbLo+Q5ugNnXWKtq3faR1fT9mLdPPzKMMYONMWm1PHcJkOx8uxd43svHDkknCgto/elPOeyIJ+WulxE3Z5Q3je7NixWXEblvmfVnqPKukhOw4S0YcK3VBALcXj+MUnBnfEoCh4tK+e5gkesNkydb6wrsXtywA+VvgdlXQ2SM1ezdLWrjB3z59+ZVwOvGkgm0FpGOPjx+0DFVVex65U7amUKKr3iJ2Fbuxw27xbUgp/sNHCeWqqV/90GVIWb9G1a2vD/dWdsI/hql4Mr4FCs9c8k2Nxn5icMhunXDhnWO7IRZV1qLvt/2oTV2HwC82fANsFBE1ohIbeEcnYF9NT7Pcz52DhG5V0SyRCSroKCBK/iEiOrohDU976f30PH13u/G0am8VH4Jjp1fWBG6yjuMsYZzOqdBp8F2V9NoxhjeX++fUQquJMRGM6BzKxa5m48fFg69JlrTMz25IbFwN8y6AjDWmX09g+f8gTcb/hhjzFCsoZv7ReT8ZX1q+3vwB4NsxpiXjDFpxpi0+Ph4L5YXXL6PThjCiFt+79G+GakJfBlzJcUSY2VzK+/Y87WVxDjCwyUM/dTa3GPkHPXPKAV3MlITWJd7jGPFbla3Sp4CxQVwsJ4nPsdzrTP7ijPWBdr43o0v1oe81vCNMQec7/OBBcCI8zbJA2regZIIHPDW8UNJyZni76MTbpuFI8yzqNUwh3BVeh9mlE+21jI9/F0TVRpiVs+AZm2h79V2V+IV767dT3SEw2+jFFzJSImnysDSHW5GCXpNBKR+d90WHbCafUkRTH/furkqwHil4YtICxGJrf4YmAxsOm+zD4FbnbN10oETxpiD3jh+qMl+pUZ0QqeGjR3eMLwLc80llDqawzf/8HKFIejEfitnfuh0v8lNaYzvoxQ6+G2UgisDE1vTtkWk+5iFFnGQmOa+4Z/Kt5p9cQFMfy9gh+y8dYbfHlgmItnAKuA/xpjPRDFbVw4AACAASURBVOQ+EbnPuc0nwG5gJ/Ay8FMvHTukWNEJ7/4gOsFTcTFRjB6QzNzKSZjN71kXoVTDrXkNTBWk3Wl3JV5xNkphiP/PPKlNmEMY3zuer7cXUFlVj+mZ+9fCqTr+Gig+Cq9fBUX7rbiExNomIQYGrzR8Y8xuY8wg51s/Y8zjzsdfMMa84PzYGGPuN8b0NMYMMMb8YK6+cs1VdEJDTB+VxL9LL6FSImDZk16oMERVlMHaWVbjaNPN7mq8ojpK4YJe/nsTkTvjUxM4drqc9fvczLNPvggwsLOWRVHOHLOmXhbuthaNSRrVJLX6SuDfBhgiakYnRN346g+iExpiaNc2JHTswsfhkzEb5sOxHC9UGoK2fgynDgfNxdpAilJwZVxyPA7B/V23HQZBTPsfLopSUgRzfmTl7dww18q1D3CB+68ZYr6PTniMLsmDvPKaIsL0UUn8pWgyBoHlT3vldUPO6hnQOgl6TrS7Eq8IpCgFV1o1j2BYUhv30zMdDuh1EexcBJXO0LXSUzD3OjiYDdfNguRJTV+wD2jDDwDnRid499LHVYM7URzdnhWxF8O62VCk19E9cvg7yFkeNLk5EFhRCu5kpCaw+UARh4tKXG/YezKUnoB9K62VsN64EfJWwY9egdRLfVOsDwTH/9AgduLYEVp/+lPy6xmd4KnmkeFcOyyR3x2ZiKmqhG+f9errB72sVyAsCoZMt7sSrwjEKAVXMpyLorgd1ukxHhzh1kpVb95iRR1PfRH6BccU22ra8P1YzeiEU/WMTmiIaelJ7K5MYFvCxZA1E4rdRMsqS0kRZM+H/j/yOA634GQphe5uCrJBIEYpuJLaIZaOraJZvNXNfPzoVtZyhCuftxYxufLZei/u7m2FxWWszT3WJK+tDd+PrX7vKYae+trj6ARP9YyP4YJecfxf4RRMRQms+FeTHSuobHgTyk55nJtTVlHFlc8tY/jjX3LrzFW8nbWPE2fKm6jI+gvUKAVXRITxKQks23mEsgo38Ql9rrDeX/ZP634KG5w4Xc70V1Zy12ur3S/i0gDa8P1UY6ITGmJaehIrTsZxqMslsOplOF3Y5McMaNW5OZ2GQOIwj3Zd+N0hDp4o4bIBHdldcIqH39nA8D99yT2vZ/Fh9gFOl3n/B70+AjlKwZWMlHhOlVaQtdfN/+nh98AD62xbpexkSTm3vrqKHYdP8eQNg5vkhrfAu4UuBDQ2OqEhJvVJoGOraJ4tu5L/V/YJrHoJxv+myY8bsHKWW9P1rvL8r6HXV+TQpW0znrphMCKwft9xPso+yMcbDvDFd4dpFhHGxD4JXDGoE+N6xxMd0fT//mDNvQ/UKAVXxvSKIzLMwaKt+Yx2dV+BwwFte/iusBqKSyu449XVbN5/guenDTu7ILu36Rm+HzobnTD2Hw2OTvBUeJiDm0d0ZV5OS4q7T4HM560xalW71TOsaN1+13i027ZDJ1m1p5BpI5NwOAQRYUjXNjx2RV9W/HYi8+9N55qhnVm+8wg/nr2G4X/6kl++lc2SbfmUV3qQ6Oih0opKPg7gKAVXWkSFM7JHW/eLm9vkTFkld81azdrcYzxz0xAu6tu+yY6lDd/PrP9injM64UYGTfDtRaMbRnQh3CG8EX09lBy3ZqCoHzp5yJrNMWQaRHp2A9yczBwiwx1cn9blB8+FOYT0Hu14fOoAVj06iVl3jmBK/w4s3HyI219dzYjHv+S/F2xkxa6j7uMCPLR4a0FARym4k5GSwK6CYnKPnra7lHOUlFdy7+wsVu4p5J/XD+bSAU27RIg2fD+Sv38P3ZY/7IxO8H3UQUJsNBf378AzW2Kp7DEBvn3OmpOszrVmFlRVeJybc7KknPfW5nHFwE60aRHpctuIMAfjesfzxHWDWP0/k3hp+jAuSI5nwdr93PRyJqP/8hV/+Og71uUec7+UXz28tzaPuJjAjlJwJSPVGiLxp7P8sooqfjZvLd/sOMJfrxnI1T74ZasN309UVlRQMOtWr0YnNMSto7pRVFLBkva3wekjVkaM+l5lOax5FXpN8njhi/fX7ae4rJLpozwbpouOCGNyvw48e9MQ1vxuEs/eNIRBia2Zk5nD1H9/y4V/W8xfPt3K5gMnGtT8z0YpDA7sKAVXuse1oHtcC79p+BWVVfx8/jq+3JLPn67uz/XDf/gXX1MIrsG6ALZq9qOMKtvA6iGPM9xL0QkNMbxbG1Lax/LPbcKEpDHI8qetM9nwKNtq8ivbPoGTB+Fyz/4CM8bw+oocBia2YnCX1g0+fPPIcK4Y1IkrBnWiqKSchZsP81H2AV7+ZjcvfL2LHvEtuGKg9XyvhJh6vebZKIUgHc6pNj4lnnkrczlTVkmzSN9cCK9NZZXhobey+XTTIX53eV+mpftuecTg/HUeYJoyOsFTIsK0UUlsPlDEztSfWM1t/Vxba/Irq2dAq65WMqYHVu4pZEf+Ka/+cLeMjuDaYYnMunMEq/57Io9P7U9CbBTPLNrBpH9+zaVPf8PzS3axr9D1sNyCtXn0bh9Dv06BH6XgyoTUBEorqlix274bC6uqDI+8u4EPsw/wyMWp3HVBd58eXxu+zZo6OqEhpg7pTExUOM/nJFrrsy570hrKCHUF22DPUki7AxyenSHOzsyhVbMIrhjYNHewtouJ4paRScy/dxSZv53IY5f3JSrCwV8/28qFf1vM1H8v55Vle36QKVMdpXDN0MSgiFJwZUT3tjSPDHMfptZEjDH8zwebeGdNHg9OSuYn432/Fq793SWE1YxOOHnZC00WneCpmKhwrhnamY83HuLkyF9Y63hufNvusuy3+hUIi/Q4Nye/qITPNx3i+rREnwwltG8ZzZ0XdGfBT8fwza8zeOTiVErLq/jjx9+R/uevuOHFFcxdmUNhcVnQRSm4EhUexphecSzeWuCVC92eMMbwh4+/Y97KXH4yvic/n5js0+NX04Zvo9ULnmboqa/J6nk/KWkT7C7nHNPTkyirrGLO0VToMMBaBrGq0u6y7FN6CrLfsNarjYn3aNc3Vu2jospwy0jfjdVW69K2OT8Z35NPfn4hXz40jp9PTKbgVCmPLtjE8Me/5KWlu4MqSsGdjJQE9h8/w478Uz47pjGGv3y2lVeX7+XOMd359ZQU2/6a0oZvk5ytaxmw4f+xMWoII30QneCp5PaxpPdoy9xVuVRe+Cs4uhM2L7C7LPtsfAtKizxe5KS8sop5q3IY2zuebnEtmqi4+umVEMODk3rz1UPj+OSBC7l3bA+S2jXn7gvsubvUDuNTrF/Wbte69aInv9zBi1/vZlp6V353eR9bh8604dug5EwxlW/dQYkPoxMaYnp6N/KOnWGJjIS4FOdZftPd7em3jLGGczoMgMThHu365XeHOVxUyq0+nInhjojQt1NLHrk4lc8eHHt2jnoo6NS6GakdYn02jv+vxTt55qsdXJ+WyB+u7G/7dRJt+DbInvkAPar2kuvD6ISGmNyvPQmxUcxeuQ/G/gryv7OmJYaafSvh8CYrFdPDH9jZmTl0bt0spJqqv8tITSAr5xhFJU07EWHGN7v5++fbuHpwJ/58zUAcDvsvije64YtIFxFZLCJbRGSziPy8lm3Gi8gJEVnvfHussccNVOu/mMfIgndsiU7wVESYg5tGdOXr7QXkdJwCbbrD0r9bZ7yhZNXLENUKBlzn0W4780/y7a6j3JLelTA/+GFXlgmpCVRWGb7Z3nTTM19fsZc//WcLlw7owBPXDfKbf39vnOFXAL80xvQB0oH7RaRvLdt9Y4wZ7Hz7gxeOG3Dsjk5oiJtGdMUhwtzVB+DCh+Dgetj5ld1l+c6pfPjuAxh8M0R6NgY/JzOXyLDac3OUfYZ0aU2rZhFNdtftm6tzeeyDzUzq056nbxziV3cvN7oSY8xBY8xa58cngS1AcN+y1wD+Ep3gqQ6topnSrz1vZe2jpO910DIRlv4tdM7y174OVeUeZ6QXl1bw7po8Lh3QgbgYvUvZn4SHORjbO54l2wqo8nII3YJ1efzmvY2M6x3Pv24ZQoQfNXvw8hi+iHQDhgAra3l6lIhki8inItLPxWvcKyJZIpJVUOBmWbIAsmrO/9CvbAObBv+OLjZGJzTEtPQkjp8u5+PNR+GCB60x7b3L7C6r6VVWQNar1nqncZ7Nm35//X5OllYwfVS3pqhMNVJGSjxHTpWy6cAJr73mxxsO8Mu3shnVox0vTh9GVLj/TcbwWsMXkRjgXeBBY8z5QeprgSRjzCDgWeD9ul7HGPOSMSbNGJMWH+/ZfGd/tXXVFwzf8yJZsRMZftX9dpfjsVE92tErIYbZK/ZakcAx7a2x/GC343MoyvN4CUNjDLNX5NC3Y0uGdm14bo5qOuN6xyOC+7Vu6+nzzYf4+fz1DEtqw4zb0ny2aI2nvNLwRSQCq9nPNca8d/7zxpgiY8wp58efABEiEpw5rOc5cewIrT75CfmOeHr7SXSCp0SE6elJZOedIPtQKYz+L9jzNexbZXdpTWv1DGjZGXpf4tFua3KOsfXQSaaPSrJ9Gp6qXbuYKAYltmaRF8bxF2/N52fz1jKgcytm3j6c5pH+m0npjVk6ArwCbDHG/LOObTo4t0NERjiPe7Sxx/Z31dEJcc7ohJat29ldUoNNHdqZ5pFhzMnMgWF3QLO2sPQJu8tqOkd2wq5F1tca5tkP8OsrcoiNDg+JuIJANiE1gQ15xzlyqrTBr7F85xF+PGcNKR1imXXnCGKjI7xYofd543RzDDAdmFBj2uWlInKfiNzn3OZaYJOIZAPPADcaX4dZ2MCfoxM81TI6gqlDOvNh9gGOVUTCqPutIY+D2XaX1jSyZoIjAobe6tFuBSdL+XTTQa4dlujXZ3rKilkwBr7e1rBhnZW7j3LXrNX0iGvB7DtH0qqZfzd78M4snWXGGDHGDKwx7fITY8wLxpgXnNs8Z4zpZ4wZZIxJN8Z82/jS/ZepqmL1+8/5dXRCQ0xLT6K0oop31uRZEQNRrYJzLL/sNKyfA32vhFjP1hd9K2sf5ZXGpxnnqmH6dWpJXExUg6Znrs09xp2vraZz62bMuXuk2xXM/EXgDSj7uaOH81j/xOUMX/8oe6JS6HjHbL+NTvBUn44tGd6tDXNW5lAV2RJG/tha2zV/i92ledemd6DkhMcXaysqq5ibmcMFveLoGV+/xUeUfRwOISMlnqXbC6jwYIH4jXknuG3mKuJjo5h3T3pATbvVhu9F6xbOQZ4fRb/ilWT2+gWpj3xNXIfguulm+qhu5Bw9zdIdBZD+E4hoYWXsBAtjrDtrE/pC11Ee7bpoaz4HTpTo2X0AyUhNoKikgrW5x+u1/XcHipj2ykpaNYtg3j3ptG8Z3cQVepc2fC8oOn6U1U/ewJBv76cwLJ79N3xG+rTfB82ZfU0X9+tAXEykdfG2eVvrhqRN78LRXXaX5h15WXBoQ4Nzczq2imZSH83NCRQXJMcR7pB6hantOHyS6a+spHlkGG/ck06n1oEXKa0Nv5E2Lf+I00+NZMjxhaxIvJOuv/6W7n09S1QMJJHhDm4c3pWvtuZbS+eN+pm1KMiyWidoBZ7VMyAyFgZ6lnO0u+AU3+w4ws0juvrVrfTKtZbREaR1a8MSN+P4e44Uc/OMlTgcwty7R9KlbWDcKX8+/Z/ZQCWnT5H573vp/8U0yiWCXVe8y6i7nyQyKrD+xGuIm0d2RYB5q3Kti5pDb4Ps+dbKWIGs+Chsfg8G3wRRsR7tOndlLhFhwg0jgmsILxRMSE1g66GTHDh+ptbn9xWe5uaXM6mqMsy7eyQ9Avj6jDb8BtixbimHnxhJev6brIz7EXG/WhXw0y490al1Myb1ac+bq/dRWlEJYx4ABJY/bXdpjbPudagsgzTPcnPOlFXydtY+Lu7fkYTY4P+FH2wyUqwhuNpm6xw4foabXs7kTHklc+4eSXJ7z04E/I02fA+Ul5WyYubDdH//KppVnWbjhNcY+bOZNGsR2P8JGmL6qCQKi8v4ZONBaJVopUmunQ1FB+0urWGqKq25990uhIRUj3b9MHs/RSUVTNeLtQGpV0IMiW2a/SBm4XBRCTe/nMmJ0+XMvnMkfTq2tKlC79GGX08529az929jGJX7EutbTSTqgVUMGDvV7rJsM6ZnnHXDyYoc64ELfgFVFbDiOXsLa6idX1pDUg3IzXl9RQ4p7WMZ3q1NExWnmpKIkJGSwPKdRygpt9ZtPnKqlJtfzqTgZCmv3TmCAYmtbK7SO7Thu1FVWUnmvD/Rft4k4ioOsXbkU6Q99A6t2gZHsFtDORzCLelJrM09zqb9J6Btd2uBkKyZUNx0C0s0mVUvQ0wHSL3Mo93W7TvO5gNFmpsT4DJS4zlTXsmqPYUcKy5j2oyV7D9+hpm3D2dYUvD8IteG78Kh3B1s+WsG6dv/ztbmw6i871uGXnKH3WX5jWuHJhId4bCmaAJc+EsoPwOZ/7a3ME8V7rbO8IfdDmGe3R4/Z0UOMVHhXD1El4AIZKN6xBEV7uCD9QeYPnMlu48UM+PW4YzsEbj5V7XRhl+L6miEFq9cSLfSbawa8H8MevhT4jp0tbs0v9KqeQRXD+7M++v3c+JMOcT3hn5Xw8qX4Mwxu8urv6yZIA6r4Xvg6KlSPt5wkGuGdiYmSnNzAlmzyDBG9WzHu2vz2HboJC9OH8YFycEX6KsN/zw1oxH2RfbkxO1fM+JHDwZkrLEvTEtPoqTcma8DcOGvoOyk1fQDQfkZWDcH+lwOLTt6tOtbWXmUVVbpxdogceWgTkSECf+6eejZmTvBRrtYDesWzoHnR5+NRkh55Gs6dfdsxkao6d+5FUO7tmZOZo61XFyH/pByqTWsU3rS7vLc27zA+mvEw4u1lVWGuStzSO/RNuCn6inLNUMTyf7fyUzu18HuUpqMNnyc0QhP3ciQb+/neFi7s9EIYeH6Z3p9TB+VxJ4jxXy7y7nEwYW/gpLjsPoVewurj1UvQ1yKNR3TA0u25ZN37Ay36hKGQSXYI61DvuFXRyMMPfYZKxLvpMuvVwR1NEJTuKR/R9q2iOT1FXutBxKHQc8J1hTNstN2luba/jVwYG2Dc3MSYqO4qK9n8clK2SlkG37J6VNkPv/js9EIO0IoGsHboiPCuGF4F77ccvj729PHPgzFBbD2dXuLc2X1TCvtc9CNHu2Wc7SYr7cXcNOIrkRobo4KICH5v9WKRkgn/fB8VsZdQ7tfZpKaNtHusgLazSO6YoA3VjnzdJJGQ9IYK26houFLyDWZ04VW7v2gGyDaszso567MxSHCzSN11pYKLCHV8M+NRihmY8arjPzZqzSPCY676OzUpW1zJqQk8MaqfZRVOBeTGPsrOHkA1s+zt7jarJ8LFSUeX6wtKa/krax9TOnXPuCy0JUKmYafs209e/52gTMaYYIVjTDuGrvLCirTRyVx5FQpn20+ZD3QIwM6D7OikyvL7S2upqoq64Jy19HQvp9Hu36UfYDjp8t1kRMVkIK+4VdVVpL5xuO0nzeJ+IqDzmiEd0M+GqEpjE2Op2vb5sxesdd6QATG/trKqNn4jp2lnWvXIji2x1q8xUNzMnPolRDDqCC7A1OFBq80fBG5WES2ichOEflNLc9HicibzudXikg3bxzXnUO5O/jubxNI3/Y3tjUfSuW9yzUaoQk5HMK09K6s3nuMLQeLrAd7T4H2A+CbJ6xESn+wega0SIA+V3q0W/a+42TnnWB6uubmqMDU6IYvImHAv4BLgL7ATSLS97zN7gKOGWN6AU8Cf23scV2xohH+RYtXLqR7yVZWDfg9Ax/+jLhO+md4U7tuWBeiwmvk64hYY/lHd8J379tbHMCxHNj+GQy7DcIjPdp1dmYOzSPDmDpUc3NUYBJjTONeQGQU8HtjzBTn578FMMb8ucY2nzu3WSEi4cAhIN64OXhaWprJysryqJ6TJwr5/bzLKZQCTjtaEJaQQlR0YC5HFqh2FZyisLiMoV3bEOZwngnvX2vFJ0e2sLe4ylIrTqFzGoRH1Xu3ikrD2txjxMdG0T3O5q9BBb3Utqk8MuKRBu0rImuMMWm1PeeN28o6A/tqfJ4HjKxrG2NMhYicANoBP8jRFZF7gXsBunb1fNpbs+YxhFWVUhSTSGyC/ulthw4toyk4WUrBqVI6VM9kadvdGsuvqrC3OAmzFmzxoNkDFJwqpcoYnZmjApo3Gn5tHfX8M/f6bGM9aMxLwEtgneF7Wkx4RCR/uW8VjrAwT3dVXnTVc8sozqtk5i/GBvwv3aoqQ8Y/ljAgNpo3rxxldzlKNZg3LtrmATVXbk4EDtS1jXNIpxVQ6IVj10qbvf2mpSexM/8UK3YftbuURlu6o4Cco6eZNkqvAanA5o2GvxpIFpHuIhIJ3Ah8eN42HwK3OT++FljkbvxeBbYrBnWidfOI7y/eBrA5mTnExURxcRCnKKrQ0OiGb4ypAH4GfA5sAd4yxmwWkT+ISPW8t1eAdiKyE3gI+MHUTRVcoiPCuD6tC59vPszhohK7y2mwfYWn+WprPjeN6EJkeNDftqKCnFf+BxtjPjHG9DbG9DTGPO587DFjzIfOj0uMMdcZY3oZY0YYY3Z747jKv90ysitVxjBvZa7dpTTYvFW5CHDTCM3NUYFPT1lUk0lq14JxveN5Y1Uu5ZVVdpfjsZLySt5cvY9JfdrTqXUzu8tRqtG04asmNT09ifyTpSzcfNjuUjz26aaDFBaX6SInKmhow1dNanxKAp1bN2N25l67S/HY7BU59IhrweiempujgoM2fNWkwhzCtPQkMncXsuNwAKxx67Rp/wnW5h7nlvQkHI7Avo9AqWra8FWTuz4tkcgwB7MDaIrmnMwcoiMcXDss0e5SlPIabfiqybWLieLygR15c/U+5q/Kxd9vwThxppz31+/n6sGdadUswu5ylPIabfjKJ35zaSrDktrwm/c2cvesLPJP+u/c/HfW5FFSXsV0vbNWBRlt+MonEmKjmXPXSP73ir4s23mEKU8u5ZONB+0u6weqqgxzMnMY2rU1/Trp0pcquGjDVz7jcAh3jOnOfx64kC5tm/PTuWt5cP46Tpz2n+UPl+86wp4jxXp2r4KSNnzlc70SYnj3J6P5xaTefLThIFOeWso3OwrsLguwpmK2bRHJpQM62l2KUl6nDV/ZIiLMwc8nJbPgp6NpERXG9FdW8dgHmzhdZl9e/oHjZ/hyy2FuGN6FqHBNXFXBRxu+stXAxNb854ELueuC7ry+IofLnlnG2txjttQyb2UuBrhZc3NUkNKGr2wXHRHG7y7vy7x7RlJWUcW1z3/LPxZuo6zCd/k7ZRVVzF+dy8TUBLq01SUxVXDShq/8xuiecXz64IVcMzSRZxftZOq/l7PdR3fnfrb5EEdOlTEtXS/WquClDV/5lZbRETxx3SBenD6MQydKuPzZZby8dDeVVU17s9bsFXtJatecscnxTXocpeykDV/5pSn9OvD5L8Yyrnc8j3+yhZtezmRf4ekmOdaWg0Ws3nuMaSM1N0cFN234ym/FxUTx0vRhPHHdILYcKOLip5by5mrvRzPMzswhKtzBdWmam6OCmzZ85ddEhGuHJfLpgxcyMLE1j7zr3WiGopJy3l+3nysHdaJ180ivvKZS/kobvgoIiW2aM/fukTx2+ffRDJ96IZphwdr9nC6r1DtrVUjQhq8ChsMh3HlBd/7zwAUktmnOT+au5RdvrufEmYZFMxhjmJ2Zw6DEVgxMbO3lapXyP41q+CLydxHZKiIbRGSBiNT6UyMie0Vko4isF5GsxhxTqV4Jsbz309E8OCmZD7MPcPFTS1m244jHr7Ni91F25p9iui5hqEJEY8/wvwD6G2MGAtuB37rYNsMYM9gYk9bIYypFRJiDByf1ZsFPR9M8Moxpr6zk9x9u5kxZZb1fY05mDq2bR3D5QM3NUaGhUQ3fGLPQGFMdfpIJ6DQH5VPV0Qx3junOa9/u5bJnvmFdPaIZDp0o4fPNh7k+rQvREZqbo0KDN8fw7wQ+reM5AywUkTUicq+rFxGRe0UkS0SyCgr8I0FR+bfoiDAeu6Iv8+4eSUl5JT+qRzTDG6tyqTKGW0Zqbo4KHW4bvoh8KSKbanm7qsY2jwIVwNw6XmaMMWYocAlwv4iMret4xpiXjDFpxpi0+Hi961HV3+hecXz2i7FMHWJFM1zzfO3RDOWVVbyxKpdxveNJatfChkqVsofbhm+MmWSM6V/L2wcAInIbcDlwi6njjhhjzAHn+3xgATDCe1+CUt9rGR3BP64fxAvThnHwuBXNMOOb3VTViGZYuPkw+SdLma65OSrENHaWzsXAI8CVxpha73sXkRYiElv9MTAZ2NSY4yrlzsX9v49m+NN/zo1mmJ25l8Q2zRifkmBzlUr5VmPH8J8DYoEvnFMuXwAQkU4i8olzm/bAMhHJBlYB/zHGfNbI4yrlVnU0w9+vHchmZzTDk19sJ3N3IbeMTCJMc3NUiBFv55J4U1pamsnK0mn7qvHyjp3mV29nk7m7kMhwB5m/nUjbFhqloIKPiKypa/p7uK+LUcoOiW2aM+/udOatyiUyzKHNXoUkbfgqZDgcogucqJCmWTpKKRUitOErpVSI0IavlFIhQhu+UkqFCG34SikVIrThK6VUiNCGr5RSIUIbvlJKhQi/jlYQkQIgp4G7xwGer3sXnPR7cS79fpxLvx/fC4bvRZIxptZseb9u+I0hIlm6nKJFvxfn0u/HufT78b1g/17okI5SSoUIbfhKKRUigrnhv2R3AX5Evxfn0u/HufT78b2g/l4E7Ri+UkqpcwXzGb5SSqkatOErpVSICLqGLyIXi8g2EdkpIr+xux47iUgXEVksIltEZLOI/NzumuwmImEisk5EPra7FruJSGsReUdEtjr/j4yyuyY7icgvnD8nm0TkDRGJtrsmbwuqhi8iYcC/gEuAvsBNItLX3qpsVQH80hjTB0gH7g/x7wfAqnB4QQAAAhZJREFUz4EtdhfhJ54GPjPGpAKDCOHvi4h0Bh4A0owx/YEw4EZ7q/K+oGr4wAhgpzFmtzGmDJgPXGVzTbYxxhw0xqx1fnwS6we6s71V2UdEEoHLgBl212I3EWkJjAVeATDGlBljjttble3CgWYiEg40Bw7YXI/XBVvD7wzsq/F5HiHc4GoSkW7AEGClvZXY6ing10CV3YX4gR5AAfCqc4hrhoi0sLsouxhj9gNPALnAQeCEMWahvVV5X7A1fKnlsZCfdyoiMcC7wIPGmCK767GDiFwO5Btj1thdi58IB4YCzxtjhgDFQMhe8xKRNlijAd2BTkALEZlmb1XeF2wNPw/oUuPzRILwzzJPiEgEVrOfa4x5z+56bDQGuFJE9mIN9U0QkTn2lmSrPCDPGFP9F987WL8AQtUkYI8xpsAYUw68B4y2uSavC7aGvxpIFpHuIhKJddHlQ5trso2ICNYY7RZjzD/trsdOxpjfGmMSjTHdsP5fLDLGBN0ZXH0ZYw4B+0QkxfnQROA7G0uyWy6QLiLNnT83EwnCi9jhdhfgTcaYChH5GfA51lX2mcaYzTaXZacxwHRgo4isdz7238aYT2ysSfmP/wLmOk+OdgN32FyPbYwxK0XkHWAt1uy2dQRhzIJGKyilVIgItiEdpZRSddCGr5RSIUIbvlJKhQht+EopFSK04SulVIjQhq+UUiFCG75SSoWI/w8h4RCh5mxEPgAAAABJRU5ErkJggg==\n", "text/plain": ["
"]}, "metadata": {"needs_background": "light"}, "output_type": "display_data"}], "source": ["import matplotlib.pyplot as plt\n", "\n", "li = [0, 2, 4, -7, -2, 7, -1, 8, -10, 3]\n", "cumul = [li[0]]\n", "for i in li[1:]: \n", " cumul.append( cumul[-1] + i )\n", "cumul2 = [li[0]]\n", "for i in li[1:]:\n", " cumul2.append(max(cumul2[-1] + i, 0))\n", "plt.plot(cumul, label=\"cumul\")\n", "plt.plot(cumul2, label=\"cumul2\")\n", "plt.plot([0 for c in cumul])\n", "plt.legend()\n", "plt.title(\"somme cumul\u00e9e\");"]}, {"cell_type": "markdown", "metadata": {}, "source": ["La courbe devient n\u00e9gative au quatri\u00e8me nombre. L'astuce consiste \u00e0 dire qu'on peut traiter les deux ensembles s\u00e9par\u00e9ment et que la meilleure sous-s\u00e9quence n'inclura pas ce nombre en quatri\u00e8me position. Si on cherche la meilleure sous-s\u00e9quence se terminant \u00e0 la position $i$, il suffit juste de revenir en arri\u00e8re et de trouver le minimum de la courbe cumul\u00e9e avant la position $i$. Pour $i=5$, le point le plus bas qui pr\u00e9c\u00e8de est le point $k=3$. Au point $i=3$, on sait qu'il n'existe pas de sous-s\u00e9quence positive pr\u00e9c\u00e9dent $i=3$.\n", "\n", "On d\u00e9coupe la courbe en segments $[[i,j]]$ v\u00e9rifiant $l_{i-1} < 0 \\leqslant l_i$ et $\\sum_{k=1}^{j} l_k < 0$ et $l_{j+1} \\geqslant 0$."]}, {"cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [{"data": {"image/png": "iVBORw0KGgoAAAANSUhEUgAAAqAAAAGgCAIAAAD6tkIPAAAAAXNSR0IArs4c6QAAAARnQU1BAACxjwv8YQUAAAAJcEhZcwAADsMAAA7DAcdvqGQAABwTSURBVHhe7dXBlYSwdqBhB+LVnMnD21lMMI5lMnECjsCpOIY3vOb2tZoCCgoKJPF9R4tGUtGg7lP/v/wDAOiOwANAhwQeADok8ADQIYEHgA4JPAB0SOABoEMCDwAdEngA6JDAA0CHBB4AOiTwANAhgQeADt0Q+H9ZEMsAwGEVBX4QOwCAYwQeADok8ADQoaubGiUvlJPjHgDgoJsDP5kcLwGAgy5tamS8MJkfLwGAg77b1Oj2gtgEAJxN4AGgQwIPAB26obKRd4EHgK8ReADokMADQIcEHgA6JPAA0CGBB4AOCTwAdEjgAaBDAg8AHRJ4AOiQwANAhwQeADok8ADQIYEHgA4JPAB0SOABoEN3Bn4QUwDAqe5JbORd4AHgOwQeADok8ADQIYEHgA4JPAB0SOABoEMCDwAdEngA6JDAA0CHBB4AOiTwANAhgQeADgk8AHRI4AGgQwIPAB0SeADokMADQIcEHgA6JPAA0CGBB4AOCTwAdEjgAaBDAg8AHbotsVF4jQeALxB4AOiQwANAhwQeADok8ADQoTv7GoXXeAA4m8ADQIcEHgA6JPAA0CGBB4AO3RzXKLzGA8CpBB4AOiTwANAhgQeADgk8AHRI4AGgQwIPADf49//3nzli6lQCDwBXK+s+jlg4j8ADwNUmdR9HrJ1E4AHgapO0jyPWTiLwAHCpSdQnl2cReAC41KTok8uzCDwAXGc2568zx9US+EFMAUC/Zls+O3nQ/VmNvAs8AA8w2/LZyYMEHgCuM9vynJzMHyHwAHCd2ZDn5GT+CIEHgOsshTznX5c+I/AAcJ2ViufS7OpeFQV+EFMA0KmVhOfSZLWczxFrywQeAK6zXujZ1ZycjFheUEVTI+8/YgoAerSe59fVnHkdsWNBLUGNvAs8AF1bz3Ou5oYtM7MEHgCus97mXM0N6zM5+UrgAeAiW8I82VP+nHJyMl8SeAC4yNsqD3LPZMTyr5WlUUVBjcJrPACdWk9yym3liLXC+mqNgR/EFAB0ZKXHpdyWIxb+Wt8g8ABwkZUel3Jbjlh4sbKhrpRG3gUegB6t9Hgid67vX9kg8ABwhYzxbI8nNm5e2SPwAPB1WeLZGL/au/+VwAPA1x0P9l4CDwBfd3HdBwIPAF8n8CGuAaALAh/iGgDal3UXeIEHoB/X130g8ADwRVl3gf+nuAaAxt1S94HAA8AXCfw/Rd4FHoBeCPw/Rd4FHoAuZN0FPsQ1ADTrxroPBB4AvkLg/0fkXeABaNy9dR8IPACc7966DwQeAM4n8H9E3gUegMYJ/B+Rd4EHoGVZd4EPkXeBB6Blt9d9IPAAcKasu8D/j8i7wAPQrBrqPhB4ADiTwM+IvAs8AM0S+BmRd4EHoE1Zd4H/I/Iu8AC0qZK6DwQeAE4j8PMi7wIPQIPqqftA4AHgHAK/KPIu8AC0Jusu8DMi7wIPQGuqqvtA4AHgBAK/JvIu8AC0RuDXRN4FHoDWCPyayLvAA9CUrLvAz4u8CzwATamt7oOKUhpt/xFTAFC9rLvAz4u2/4gpAKhehXUf1Bj4uAaAFgj8G5F3gQegKQL/RuRd4AFoisC/EXkXeADakXUX+EWRd4EHoB111n1QS02j7T9iCgDqlnUX+EXRdnUHoB3V1n0g8ADwIYF/I9qu7gC0I+su8Isi7wIPQDsE/r3Iu8AD0IjK6z64v6nR9h8xBQB1E/j3ou3qDkA7Kq/7QOABYJ+su8CvibwLPACNqL/uA4EHgB2y7gL/RuRd4AFoQRN1Hwg8AOwg8FtF3gUegOpl3QX+vci7wANQt7LuAv9e5F3gAahYW3Uf3JzVaPuPmAKA+rRV90EtgY9rAKhSW3UfCDwAvJF1F/itIu8CD0DFBH63yLvAA1Axgd8t8i7wAFSsuboPBB4A3hD43SLvAg9AxQR+t8i7wANQMYHfLfIu8ABUTOD3ibarOwAVy7oL/FaRd4EHoGIt1n0g8ACwRuB3i7wLPAAVE/jdIu8CD0Ctsu4Cv0PkXeABqFWjdR8IPAAsEvhPRN4FHoAqtVv3gcADwDyB/1DkXeABqJLAfyjyLvAA1Kfpug8EHgBmCPznIu8CD0B9BP5zkXeBB6A+Av+haPuPmAKAOmTdBX63aLu6A1Cf1us+EHgA+CPrLvCfiLwLPACV6aDuA4EHgD8E/pDIu8ADUBmBPyTyLvAAVEbgD4m8CzwAlRH4QyLvAg9AZQT+kMi7wAP81UddmtbHn0DgASqSaWm9Lk3r408g8AAVybS0Xpd2dfMnEHiAWpRpGUcscKFuDl/gAWqRackRC1yom8MXeIBaZFpyxAIX6ubwBR6gCtmVcsQaF+rm8AUe4GZZlNkRm7hET8cu8AA3y6iUaZlcco2ejl3gAe6URckxmR8vuUCeeR/HLvAAd1qKyuwkX9XZmQs8wJ0yKpOuLM3zPZ0duMAD3GklKitLfENnBy7wALfJosxGZX2Vc/V32gIPcI+yKEtRWV/lRP0dtcAD3COLshKVtxs4RZ5zT0ct8AAn2FuIjfs3buOgLs9Z4AHeexuAtxtK5eb1/Ru3cVCXhyzwAO9lAJYaUG5Y2jPauC3t2sxnujxkgQd4LwOw1IBywzhi4a+3G17t3c9eecKdHbLAA7xXNmA2A5MNw4iFv95ueLV3P7vk8fZ3yAIP8N7bDEw2DCMW/lpfnZUf2fUpNur4eAUe4I2yAeOIhcJkwzBiobC+uuKzT7FFx2cr8ABvZANyxEJhsmEYsfBrfXXdZ5/irb4PVuAB1mQDJiOWf01WhxELv1aW3vr4g6zr+2AFHmBNNmAyYvnHZGkcsfZraX6LI59lRd8He2dfo/AaD1Rs0oC8nJ0px7ialua3OPJZlnR/qgL/FP/9r/87R0wB72QDMgNvZ8qfS0vzWxz5LEu6P1WBf4Sy7gIP2802YDK5dJkzg9nJXQ5+nIk8z46PVOD7N6n7MGIBWLXUgHKy/HmUM28ndzn4cUp5mH2fp8B3bpL2ccQasGopA+Vk+fMoZ2Yn43q/43cgPeQwBb5bk6iXI3YAq5YyUM6XP6fXydeZvY7fgfSQwxT4Ps0W/XUGWLGUgZwvR6z9eJ2fXH4g73DkJgyec4wC36ey5WXOZyeBWUslyPlyxNqPyfzk8mOn3ITnHKPAd6is+CTkK0vAxFIJcj5HLBQmG8YRa5868VZP9pwzFPjevE34+iqQlkqQ87Oro8meccTaASfe6pkedYAC35Uy3iv9frsBGKzEIJdmVwflhnHEwjGn3/BpHnV6At+VLPfbeG/cBo+VJfg4BuUdPr7Jq9Nv+CiPOj2B70c2e0u2d22GB8oSfByD8g4f3+TV6Td8jqcdncD3Y1ewc/P2j8BzZAkqjEG1D1a/px2dwHfig1p/8BF4iCxBhTGo9sHq97SjE/hOfJbq/NTeD0LHMgN1lqDyx6vWAw9N4HtwpNNHPgtdyhLUGYPKH69aDzw0ge/BwUIf/Dh0pv4S1P+EFXrgoQl8847nOe9w5CbQjfpLUP8TVuiBhybwbTurzafcBPpQfwnqf8IKPfDQBL5hWeXjYT7xVtC6+ktQ/xNW6IGHJvCtKpN8SpVPvBU0rf4S5BPW/JBVeeaJCXyTMsYnJvn0G0KLmihBEw9ZlWcel8C3pyzxuTH+0m2hIVmCymPQxENWIs/qaccl8O35aoa/d2doQislaOU5a5Bn9bTjEvjGZIC/1OBv3x8q10oJWnnOGjz2rAS+JdfU95rfAnVqJQatPGcNHntWAt+MK7t72S+C2rQSg3zO+h/1Xk8+KIFvQxb3muhe+bugHm3FoKFHvUse0TNPSeDbcH1xr/+NcLu2YtDW094ij+iZpyTwDcjWXpnb638j3K6tGOTTtvLAF3M+At+AW1qbv/Ti3ws3aq4H+cANPfM1nMxA4Gt3Y2Vv/NVwvRaT0OIzX8PJDAS+apnYWyp772+HK5U9aCsJLT7zt+WZPPxYBL5qt/f19geAa5RJaKsKLT7zV+WBOBOBr9rtfb39AeACTSeh6Yc/XXkaDkTg61VDXGt4Bvi2ppPQ9MOfqzwKpzEQ+HrVENcangG+rfUktP78Z8lzcBQjgd8tm/fV7F3zW96q4Rnge8oktFuFDl7hOIfwSuD3yeCVI9bO89Wb71LJY8CX9FGFPt7iICfwSuD3yeCVI9bO870771XPk1zv3/7Pf+WIKbqTVWg9DH28xcfy9R97ArMEfoes3Ri88udd8oM5YuHX0vz16nmSi5V1zxFrdKSbKnTzIh/Id3/m668Q+B2ydmPwJpdblB+ZjNhRWVOrepgrTdI+jlijI92EoZsX2Stf/Jmvv07gd3itXc6Uk0vKza8jNgl8BSZRL3+mM92EoZsX2euxL76FwG81m7qcnMxPlNvGEQsvt83LnLldbc/zbZnzLPrkkp50k4duXmSXZ771dgK/1VLncn59KUes/ZrMTy5rUOEjfU+2vCz65JKedFOIfJEO3mWjB77yXgK/SUbutXPlUrk6mR9HrBUmS5PLGlT4SK+ywTliYafZO8xO0oGeCtHTu2z0wFfeq4rAD2KqVuuRy9Xc8zqzZLJnclmJOp+qVDZ4HLGw0+zHc/J1iaZ1Voie3uWtfNmHvO9nbi5r5L3uwGfeVgpX7pmM2LGg3JY/j5f1qPOpSpMGjyPW9lj6bM7PrtKi/grR2euse9TLfqyWwA9iqj5b8pZ7JiOWl032jyPWqlHtg6VJgMcRa3usfDaXZldpS+ahp0h09jrrHvWyH7s/q5H3xgM/yp1bNo/Kj+SItWrU/GyDSXonl9utfypXlzbQkMxDT4Xo741WPOplP/aUwJeJ2lWpDz6yS94/RyxUptrHe+3u68xGbz/1dgNNyDZ0locuX2rJo172Y48IfMYpRyxs8MFHdsn754iFylT7eBnd7G45k5NvbfnI2w00IdvQWR56fa9Zz3nTIwT+jQ8+skveP0csVKbaJ5yNbk5O5lds2b9lDzXLKvTaho5fbeI5b3rEQwM/jFhbtWvzZ/JXfPW3nKLC58zivkZ3aX7Jlv1b9lCzrEKvbej41Sae86ZH9B/4zNJYpsnluu07P5a/4qu/5Sy1PWoW9zW6K0uztmzOPevbqFZWodcw9P12pee86RGdBz6DVGZpcrkkt73d+Ry1nclKcVeWZm3ZnHve7uR6+Y2/8qX/dkPrun/B9Jw3PeIpgY/rH7OTrzZue5qqjmW9teurExs357a3O7lSft3niIW/1lc7kC/Y8TsOHvKax/Uc+EzRpEZL86Ute56pqpNZb+36ail37toc13zTxq/ycts4YuGv9dUO5At2/I6DJ7zjKboNfNmh1xQtzae3G54sD+fe88nQLrV2fTXlti2bB9t3clB+j+eIhReTbeOItcLKUje6f8d8wY7f8Sx9Br4s0GyEVpYGubq0gRrO521oc8PBPRN79/OZ8nu8HLH8V7la/lzK+delnnT/jt2/4IkqCvwgpg7L/CwV6MgqgxqO6G1oc8PSnrcbZn3wET6Q3+OTEct/lav583iZluY7s/KOK0sN6eMtrnF/4AeR9y8EPq5frG9YX2WQR3TjKW0J7cqeXFrasOSDj/Dq7df0ZMPkspRL4+rkMs1O9mflNVeWWpGv0PRbXKa3wJfhWW/P0p6leSZuP6gtoV3Zk0uzqys++xSl8mt69pv6dfV1ZlTO59KWmV6tvObKUhPy+Zt+iysJvMB/KA/qrrPaEtrcM9m2NL/Fxx8kTb6phxELP2bny8ml+Zj6MZmcXHZs5U1XlprQ+vNfr+fAx9SC2W05OZnnVXlWtxzXltDmnnLb7OR2Bz9Ofk2XI9Z+7Jp/nRlN5ieXHcs3fX3ZlaUVn33qdJU8Rlu6Cvyu3szunJ1kSR7X9Se2PbGTnXlZTu5y8ON9K7+Fl76IJ3vGEWs/ZidHk6W8zJk0mZ9cdizf9PVlV5ZWlJ/a9cFZk7sNIxZWffARBv0EvozNlt7M7pydZEWe2MWHtj2xk515mTMfOH6H/ky+gscRa4XJavlzmp0c5dK4OrksTZbKn/uWb/r6suVSjlhbtnf/ismtcsTysu07KfUZ+Jha9br5dYYtbjm37Ymd7JxcfuaUm3Qmv4InI5Z/TebzcmWmVK6WI5b/muwZR6x1bel9y/lyxPKCXZvXTW6VI5YXbN/JRCeBz8Zsz8zr/tcZtshzu/Lotie23Fn+fMRZ9+lG+RX8OmLT3Df1ZGZyOavckyPW/prsGUesdW3lfculHLG2YNfmwdLOnB+XJpcrtu9koq7AD2Jqj88C8/qR1xk2uv7otic2d5Yj1j514q36MPkKLi/HmS2Tr5ezyj3jiIU5k53DiIXeLb1vzpcj1hbs2jxY2vw6P7lcsnEbr7oKfFxvVn6w/Jm98vQuO8Dtfc2d5Yi1T517tw7MfgXn5Dg/uUzlfI5YmzPZOYxYoLB0PuVk+fOK3LZl82B28/pkXM/ZsoclVQR+EHnfH/gjaSk/WP7MBy4+wF1xzc0b979V3vCsezZt9ls4Jycjln9NVscRa3MmO4cRCxRmz2cyObmcVe4ZRywsm928PhnXL3LDyh5WtB34jMpnXSk/W/7MB/IALzjDSuJayWPcbulbuJwvRywXJhuGEQsc8HqYOTNOTi5flRvKEctzJjuHMZkfL0c5OZkflauzG3ir4cCfUpTyJkfuw+CyY6wkq/kYtz/JXSZfwcOIhV+T1WHEwl9b9rDX63nmTE5OLku5lBvKn5fknhyT+fFylJO7ltiu1cBnSw7mpLzPwVtx2UlWktV8jNuf5C4bv4XP2sMur+e5MlNODmbnZycnyj3jmMyPl6OcXF+KKfZrMvBlSA625MRbMbjmJOvJaj5JDQ9zve3fwhu3caI88zz2yeUgZ8r515m0sjQqN4xjMj9elmaXZifZq/nAx9QBJ96Kaw6znqbmk1TyPFfKr+At38Lbd3KWPPM8+fLnUc4sjdj3a2VpUK4ujdhaeF19neEz7QU+E3JWRc69GxecZ1VBzYep5Hku41u4fpO/UflzysnXETv+WtpQzq+M2F2YrJaX4wwfayzwGY8T+3H6DR/ugvOsKqj5MPU80gV8Bbei/DOVP5dyvhyx9mJpz2S+vMwx7nxVbsifx0uOaCnwWY6vxoODLvgbVVjTCh/pe8qvYN/ClSv/TOXPR+R9ylutzOSIhReTbeOINQ5oMvBxTa2++peqM6X5VLU92Ol8C7el/EuVPx+R98lbvc6MyvnJUmmybRyxxgHNBD6b8aVscKKv/qXq7Gg+VW0Pdi5fwc2Z/MnGEWufmtxtMmLTHpM7DCMWOKaNwGcwvtQMzvW9P1a1Ha32wc7lK7g55Z8sR6wdMLlhjlimDo0FPq6pW/69zv2TVR7Rmp/tLL7HW5R/tRyxcMzknsOIBarRQOC/VAu+6ht/ssoLWvnjHeer/BbxzfgrZitQ/j/4l6hT7YHPTpybCr7tG3+1ygta+eMd56v8FvHN+FeswaqqA5+ROLcTXOAbf7vKC1r54x0n8LeIb8YXsQzL2gh8XNOU0/98lRe08sc7TuBvFN+Pf8UaLKg38JmHEwvBlc79C2Y+qy1oJU/4v/7j/5YjZs8g8LeLb8lCLMCcSgN/bhu4y1l/xEraue72h5ykfRyxdljWXeBvF9+Vv2IWXtQe+PGSRuXf8eCf8t5wbnfjc066Xo7YcYzAVyW+Ln/EFLzY/c8R/1PfVFYhpv6KR6EF5V8zpva7MZy73Pick6hPRmw6QN2rEl+Fv2IW/tr6nxH/R99X9iCmzhavxFXyDxrXO91Yzb1ufNTXnL/OfCzrLvCXiW+rOa8bxhmYeGLg18ULc578g8b1TjdWc6+7HnWp5Uvze6n7leKbaI/4JPz1SeBj6lRx6yLwsTAntt4kHoLNtvxNl2Qyr6/mB+561KWQl/OTpV0E/hrxFbNffB7+quU/I/5PL/lPjd/0BfEL+OuUwMf1GeKv9QX5tHG9IJ7jPCsVL5deVzcS+K+Kf4sFselHTM2JHVCo5d8i/knr+DeNRzlD3PHZMvB7G5+9HEZM7RR/hqvk08b1qnjEM6z0O5eWNmwh8N8T/w1zYsey2PcjpqBQy79F/JM28m8az/qRuMXDHAx8XK+K871VPnBcbxBPf8zbfueGlT0rBP5c8bdfEJu2ic8IPHNq+beIf9LG/03jHT4Vd+lRBn5sfLzwsizl3l5uMT7SN+QDx/WceIg5sWO/t/HODevblgj8WeIvPSd2vBO7X8QyFGr5t4h/0u7+TeOtDogbNShe4EcZ+JhalpnMEQv7xaNcpXzmmFoQz7cs9m3ztty5YX3brKy7wH8m/qKrYuuC2LQqtkKhln+L+Cd9wL9pvOen4i7ViMfa4NuBjwe6VfnMMfVOPP028Zm/Npa73La+s1TWXeA3ir/Wqti6TXxmVWyFQi3/FvFP+ux/0ziCTpWBjxde8EEm6/Hxk4+ntNfebG/fPEn7MGLh2eLcD4gb7RGfLMQCrBL42sW5NChe4FcGPq47lYH/oPGlOMRVZa3HEQvLtm+e1D1mWxAn+Km4y9ni7nAhgW9MHFM14rE2yMD33fizAj8rDv3X9lqn8iPrn2o38DWIPxjcSuC5SBl4jT/FxlRPfPYpRnH00AKB5zoPDPy3G/+BMvDDiNmOxFfJAXEjaJzAc6knBH5Qc+AH3TceGAg8l8rAP6fxcV2TSeCHEQtARwSeSwl8PQQe+ibwXO0hjc/AV9t4gYe+VRf4QUzRKYGvh8ZDxwSeq5WB1/h7CTx0rKKaRt5/xBSdEvh6aDz0qq6URt4F/gE0vhJl4DUeeiLw3EPg6yHw0CWB5x4PCfxA44FbCDy3Efh6lIHXeOiDwHObhwR+oPHA9QSe22Tgu298E4EfCDz0ROC5TRn4vhtfBl7jgWtIKbeZBH4YsdAjgQcuJvDc6ZmBr7nxAg/dEHhu9pDAj+oPPNANged+Ag9wOoHnfhn47hufgdd44NsEnvuVge+78WXgNR74KoGnCs9sfEwBfIHAU4uHNL4MvMYD3yPwVETjAc4i8NTlCYEfaDzwbQJPdR7Y+JgCOI/AUx2BBzhO4KnOQwI/0HjgewSeGj0w8BoPnEvgqdFDAj8QeOBLBB5upvHANwg83EzggW8QeLifwAOnE3i4XwZe44GzCDzcT+CB0wk8VEHjgXMJPFRB4IFzCTzUQuOBEwk8VETjgbMIPFSkDPw4YgFgJ4GHukwCP4xYANhD4KE6Ag8cJ/BQI4EHDhJ4qJTGA0cIPFRK4IEjBB7qpfHAxwQeqibwwGcEHqqWgdd4YBeBh6qVgdd4YDuBh9ppPPABgYcGaDywl8BDGzQe2EXgoQ0CD+wi8NAMgQe2E3hoicYDGwk8tETggY0EHhqj8cAWAg+NKQOv8cASgYf2CDzwlsBDe8rAazwwS+ChSQIPrBN4aFIZeI0HXgk8tErjgRUCDw3TeGCJwEPbBB6YJfDQPI0HXgk8NE/ggVcCDz0QeGBC4KEHGXiNB0YCDz0QeGBC4KEHAg9MCDx0QuOBksBDJ8rAazwg8NAPgQeSwEM/BB5IAg8AHRJ4AOiQwANAhwQeADok8ADQIYEHgA4JPAB0SOABoEMCDwAdEngA6JDAA0CHBB4AOiTwANCdf/zj/wOY0up2HDzZ7wAAAABJRU5ErkJggg==\n", "text/plain": [""]}, "execution_count": 9, "metadata": {}, "output_type": "execute_result"}], "source": ["from IPython.core.display import Image\n", "Image(\"sommemax.png\")"]}, {"cell_type": "markdown", "metadata": {}, "source": ["On parcourt la s\u00e9rie cumul\u00e9e. A chaque fois qu'on passe sous z\u00e9ro, au premier nombre positif suivant, on red\u00e9marre \u00e0 z\u00e9ro. La sous-s\u00e9quence de somme maximale est forc\u00e9ment dans un de ces tron\u00e7ons, elle a pour point de d\u00e9part le premier \u00e9l\u00e9ment et pour point d'arriv\u00e9e le maximum obtenu sur le tron\u00e7on en question : pour chaque point $x,Cumul2(x)$ d'un tron\u00e7on, le minimum de la courbe cumul\u00e9e pr\u00e9c\u00e9dent $x$ est n\u00e9cessairement le premier \u00e9l\u00e9ment du tron\u00e7on."]}, {"cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["[7, -1, 8]\n", "[78, 9, 7, 7]\n"]}, {"data": {"text/plain": ["[7, -1, 8]"]}, "execution_count": 10, "metadata": {}, "output_type": "execute_result"}], "source": ["def plus_grande_sous_liste_n(li):\n", " meilleur = [None for i in li]\n", " somme = [None for i in li]\n", " best = None\n", " \n", " for i, el in enumerate(li):\n", " if el >= 0:\n", " if i > 0:\n", " somme[i] = max(somme[i-1], 0) + el\n", " meilleur[i] = meilleur[i-1] if somme[i-1] >= 0 else i\n", " else:\n", " somme[i] = el\n", " meilleur[i] = i\n", " if best is None or somme[i] > somme[best]:\n", " best = i\n", " else:\n", " somme[i] = (somme[i-1] + el) if i > 0 else el\n", " if somme[i] >= 0:\n", " meilleur[i] = meilleur[i-1]\n", " \n", " i, j = meilleur[best], best+1\n", " return li [i:j]\n", " \n", "li = [4, -6, 7, -1, 8, -10, 3]\n", "m = plus_grande_sous_liste_n(li)\n", "print(m) # affiche [7, -1, 8]\n", "\n", "li = [1, 2, 3, 4, 5, -98, 78, 9, 7, 7]\n", "m = plus_grande_sous_liste_n(li)\n", "print(m)\n", "\n", "li = [0, 2, 4, -7, -2, 7, -1, 8, -10, 3]\n", "m = plus_grande_sous_liste_n(li)\n", "m"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Comparaison des temps de calcul\n", "\n", "On effectue cela sur une liste de nombres al\u00e9atoire n\u00e9gatifs et positifs."]}, {"cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [], "source": ["import random\n", "li100 = [random.randint(-10, 50) for i in range(0,100)]"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Co\u00fbt en $O(n^3)$ :"]}, {"cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["14.4 ms \u00b1 1.12 ms per loop (mean \u00b1 std. dev. of 7 runs, 100 loops each)\n"]}], "source": ["%timeit plus_grande_sous_liste(li100)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Co\u00fbt en $O(n^2)$ :"]}, {"cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["519 \u00b5s \u00b1 58 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 1000 loops each)\n"]}], "source": ["%timeit plus_grande_sous_liste_n2(li100)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Co\u00fbt en $O(n \\ln^2 n)$ :"]}, {"cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["146 \u00b5s \u00b1 16.9 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 10000 loops each)\n"]}], "source": ["%timeit plus_grande_sous_liste_nlnn2(li100)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Co\u00fbt en $O(n)$ :"]}, {"cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["68.2 \u00b5s \u00b1 8.44 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 10000 loops each)\n"]}], "source": ["%timeit plus_grande_sous_liste_n(li100)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Application"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Le [drawdown](http://en.wikipedia.org/wiki/Drawdown_%28economics%29) est un indicateur de performance pour les syst\u00e8mes de trading. Il mesure la perte maximale enregistr\u00e9e sur une p\u00e9riode. En d'autres, il correspond \u00e0 la sous-s\u00e9quence de somme minimale. On vient de montrer qu'il n'est pas plus long \u00e0 calculer qu'une moyenne."]}, {"cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [], "source": []}], "metadata": {"kernelspec": {"display_name": "Python 3", "language": "python", "name": "python3"}, "language_info": {"codemirror_mode": {"name": "ipython", "version": 3}, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.2"}}, "nbformat": 4, "nbformat_minor": 2}