max_contiguous_subsequence.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Maximum Contiguous Subsequence #\n",
    "\n",
    "This is a solution to Problem 6.1 in [*Algorithms*](https://www.amazon.com/Algorithms-Sanjoy-Dasgupta/dp/0073523402) by Dasgupta, Papadimitriou, and Vazirani (DPV).\n",
    "\n",
    "Given a list $S$, we want to find the contiguous subsequence of $S$ with maximum sum.\n",
    "\n",
    "**Example:**\n",
    "\n",
    "$S = 9, -10, 31, 5, -20, 19$\n",
    "\n",
    "$mcs = 31, 5$\n",
    "\n",
    "### Step 1: Define the subproblem in words ###\n",
    "\n",
    "$T(i)$ is the maximum contiguous subsequence in $S_1, ... , S_i$ *with the additional constraint that the subsequence ends at $S_i$.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 2: Find the recurrence relation ###\n",
    "\n",
    "Let's say we're trying to come up with a dynamic programming way to define some arbitrary entry *i* in our table $T$. We'll call this entry $T(i)$.\n",
    "\n",
    "The crux of this step is that we are trying to figure how we can define $T(i)$ using entries in the table $T$ that the algorithm has already calculated by the time it gets to the step of calculating $T(i)$. \n",
    "\n",
    "In this case, $T$ is a one-dimensional array and we're filling it in from left to right, so the earlier entries in the table are $T(1)$ through $T(i-1)$. *(Note: in more complex DP problems you might have to iterate over multidimensional tables in other ways such as diagonally, but this problem is straightforward.)*\n",
    "\n",
    "We defined the subproblem above to include the constraint that $T(i)$ holds the value of the max contiguous subsequence from $S_1$ to $S_i$ and *including* $S_i$. \n",
    "\n",
    "So what does that tell us about the table entry $T(i-1)$? We know that it holds the value of the max contiguous subsequence ending at $S_{i-1}$.\n",
    "\n",
    "What do we know about the subsequence ending at $S_i$? Because that subsequence ending at $S_i$ has to include $S_i$, we have two choices: either it extends the subsequence ending at $S_{i-1}$ or it is a new subsequence both starting and ending at $S_i$.\n",
    "\n",
    "Since we very conveniently know the value of the max contiguous subsequence ending at $S_{i-1}$ (hint: it's stored in $T(i-1)$), we can simple choose the larger of that combined with $S_i$, or just $S_i$ by itself:\n",
    "\n",
    "$$\n",
    "T(i) = \\max(S_i, T(i-1) + S_i)\n",
    "$$\n",
    "\n",
    "And that's a nice, handsome recurrence relation! \n",
    "\n",
    "***We're doing dynamic programming... defining the answer to step $n+1$ based on the answer to step $n$!***"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 3: Translate into code ###"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[10, -5, 40, 10]\n",
      "[5, 15]\n",
      "[5, 15]\n",
      "[500]\n",
      "[20, 15, -30, 500]\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "\n",
    "def max_contiguous_subsequence(sequence):\n",
    "    \"\"\"Return the maximum sum contiguous subsequence.\n",
    "\n",
    "    :param sequence: sequence to consider\n",
    "    :return: list containing maximum sum contiguous subsequence of sequence\n",
    "    \"\"\"\n",
    "    table = np.zeros((len(sequence)), dtype=int)\n",
    "    max_contig_subseq = []\n",
    "    for idx, value in enumerate(sequence):\n",
    "        if idx == 0:\n",
    "            table[idx] = value\n",
    "        else:\n",
    "            table[idx] = max([table[idx-1] + value, value])\n",
    "\n",
    "    # Get the index of input sequence where the maximum sum subsequence ends\n",
    "    max_seq_end_idx = np.argmax(table)\n",
    "\n",
    "    # Build list of the maximum sum subsequence\n",
    "    s = 0\n",
    "    idx = max_seq_end_idx\n",
    "    max_sum = table[max_seq_end_idx]\n",
    "    while s != max_sum:\n",
    "        max_contig_subseq.append(sequence[idx])\n",
    "        s += sequence[idx]\n",
    "        idx -= 1\n",
    "    return max_contig_subseq[::-1]\n",
    "\n",
    "\n",
    "def test_max_contiguous_subsequence(tests):\n",
    "    \"\"\"Test a series of sequences.\n",
    "\n",
    "    :param tests: a list of dicts, each dict its own test and each containing a \"sequence\" and \"answer\"\n",
    "    :return: None\n",
    "    \"\"\"\n",
    "    for test in tests:\n",
    "        seq = test[\"sequence\"]\n",
    "        ans = test[\"answer\"]\n",
    "        m = max_contiguous_subsequence(seq)\n",
    "        assert m == ans, \"Subsequence %s fails to match expected subsequence.\" % m\n",
    "        print(m)\n",
    "\n",
    "        \n",
    "test_suite = [\n",
    "    {\"sequence\": [5, 15, -30, 10, -5, 40, 10, -500, 50, -10, 10], \"answer\": [10, -5, 40, 10]},\n",
    "    {\"sequence\": [5, 15, -30], \"answer\": [5, 15]},\n",
    "    {\"sequence\": [-30, 5, 15, -30], \"answer\": [5, 15]},\n",
    "    {\"sequence\": [-30, 5, 15, -30, 500], \"answer\": [500]},\n",
    "    {\"sequence\": [-30, 20, 15, -30, 500], \"answer\": [20, 15, -30, 500]}\n",
    "]\n",
    "\n",
    "\n",
    "test_max_contiguous_subsequence(test_suite)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 4: Analyze runtime complexity ###\n",
    "\n",
    "The input to the MCS problem is the sequence $S$ and the size of that input is $n = |S|$.  \n",
    "\n",
    "We iterate over the input a total of one time to build the table $T$. That takes $O(n)$.\n",
    "\n",
    "Then we find the $argmax$ of $T$, to get the index of the last value in the max subsequence in $S$. This could potentially require us to iterate over the entire table $T$ (which is the same length as our input), so this too is $O(n)$. (The *np.argmax* function is doing the iterating for us, so we don't see an explicit for loop... but it's there.)\n",
    "\n",
    "Then we iterate *backwards* along $S$ starting at that index for the last value in the max contiguous subsequence, and keep track of value we encounter (and their sum) until we arrive at what we already know to be the total value of that max contiguous subsequence--then we stop. (Hint: we know the value from $\\max(T)$, which is stored at $T(argmax(T))$. \n",
    "\n",
    "This last step enables us to build the actual list of values in the MCS. This could potentially also require us to iterate through all of $S$... specifically, if the max contiguous subsequence starts at $S_1$ and goes until the very end. Thus, this step is also $O(n)$.\n",
    "\n",
    "So $O(n) + O(n) + O(n) = O(3n)$. And $O(3n)$ just reduces to $O(n)$.\n",
    "\n",
    "Therefore, the runtime complexity of our algorithm above is $O(n)$.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "\n",
    "\n",
    "*find all the dynamic programming notebooks at: [github.com/jonathanmcmahon/dynamicprogramming](github.com/jonathanmcmahon/dynamicprogramming)*"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.6",
   "language": "python",
   "name": "python_3.6"
  },
  "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.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}