X-Git-Url: https://git.njae.me.uk/?a=blobdiff_plain;f=monotone-substrings%2Fsingle_substring.ipynb;h=c800ab91a5c74b0a8ef48c6fc12230b3e2d3431d;hb=d86fa55df646b2374b032f3cc435cd4d8ddabf39;hp=9fb72850f45faa4e540b95173ddbe7c3b12f05b4;hpb=4be776e6aef6b347a2ee84820f5e658e517cf43a;p=ou-summer-of-code-2017.git

diff --git a/monotone-substrings/single_substring.ipynb b/monotone-substrings/single_substring.ipynb
index 9fb7285..c800ab9 100644
--- a/monotone-substrings/single_substring.ipynb
+++ b/monotone-substrings/single_substring.ipynb
@@ -1,5 +1,33 @@
 {
  "cells": [
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "# Monotone substrings\n",
+    "\n",
+    "Given a list of numbers, find the length of longest increasing or decreasing substring in the list.\n",
+    "\n",
+    "For instance, the sequence\n",
+    "  10, 1, 2, 3, 4, 5, 5, 5, 6, 4, 3, 5, 6\n",
+    "contains these increasing or decreasing substrings:\n",
+    "* 10, 1\n",
+    "* 1, 2, 3, 4, 5\n",
+    "* 5, 6\n",
+    "* 6, 4, 3\n",
+    "* 3, 5, 6\n",
+    "\n",
+    "As an extension, allow the substring to contain runs of identical numbers, each of which is included in the length of the longest substring.\n",
+    "\n",
+    "If identical numbers are allowed, the above sequence contains substrings:\n",
+    "* 10, 1\n",
+    "* 1, 2, 3, 4, 5, 5, 5, 6\n",
+    "* 6, 4, 3\n",
+    "* 3, 5, 6\n",
+    "\n",
+    "The list is given as a single line of comma-separated integers. "
+   ]
+  },
   {
    "cell_type": "code",
    "execution_count": 1,
@@ -119,7 +147,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 4,
+   "execution_count": 8,
    "metadata": {
     "collapsed": false
    },
@@ -147,7 +175,7 @@
        "5"
       ]
      },
-     "execution_count": 4,
+     "execution_count": 8,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -158,7 +186,47 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 5,
+   "execution_count": 9,
+   "metadata": {
+    "collapsed": false
+   },
+   "outputs": [
+    {
+     "name": "stdout",
+     "output_type": "stream",
+     "text": [
+      "   2 False\t10\t>\t1\n",
+      "   2 True\t1\t<\t2\n",
+      "   3 True\t2\t<\t3\n",
+      "   4 True\t3\t<\t4\n",
+      "   5 True\t4\t<\t5\n",
+      "   1 True\t5\t=\t5\n",
+      "   1 True\t5\t=\t5\n",
+      "   2 True\t5\t<\t6\n",
+      "   2 False\t6\t>\t4\n",
+      "   3 False\t4\t>\t3\n",
+      "   2 True\t3\t<\t5\n",
+      "   3 True\t5\t<\t6\n"
+     ]
+    },
+    {
+     "data": {
+      "text/plain": [
+       "5"
+      ]
+     },
+     "execution_count": 9,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "longest_monotone([10,1,2,3,4,5,5,5,6,4,3,5,6], debug=True)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 7,
    "metadata": {
     "collapsed": false
    },
@@ -174,8 +242,9 @@
       "   5 True\t4\t<\t5\n",
       "   6 True\t5\t=\t5\n",
       "   7 True\t5\t=\t5\n",
-      "   4 False\t5\t>\t4\n",
-      "   5 False\t4\t>\t3\n",
+      "   8 True\t5\t<\t6\n",
+      "   2 False\t6\t>\t4\n",
+      "   3 False\t4\t>\t3\n",
       "   2 True\t3\t<\t5\n",
       "   3 True\t5\t<\t6\n"
      ]
@@ -183,16 +252,16 @@
     {
      "data": {
       "text/plain": [
-       "7"
+       "8"
       ]
      },
-     "execution_count": 5,
+     "execution_count": 7,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
-    "longest_monotone([10,1,2,3,4,5,5,5,4,3,5,6], allow_same=True, debug=True)"
+    "longest_monotone([10,1,2,3,4,5,5,5,6,4,3,5,6], allow_same=True, debug=True)"
    ]
   },
   {