{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem statement\n",
    "\n",
    "Q: *Longest increasing subsequence* — Find the longest monotonicly increasing subsequence in a sequence."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Brute force pseudocode\n",
    "\n",
    "```\n",
    "function lis(seq, result=[], prior_subseq=[], prior_subseq_idx=[]):\n",
    "    prior_max, prior_max_idx = prior_subseq[-1], prior_subseq_idx[-1]\n",
    "    next_subseq = seq[prior_max_idx]\n",
    "    remaining_idx = argwhere({v > prior_max for v in seq})\n",
    "    for idx in remaining_idx:\n",
    "        potential_results = lis(seq, result, prior_subseq + [seq[idx]], prior_subseq_idx + [idx])\n",
    "        if len(potential_result) > len(result):\n",
    "            result = potential_result\n",
    "    return result\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      ".....\n",
      "----------------------------------------------------------------------\n",
      "Ran 5 tests in 0.002s\n",
      "\n",
      "OK\n"
     ]
    }
   ],
   "source": [
    "import unittest\n",
    "\n",
    "class TestLIS(unittest.TestCase):\n",
    "    \n",
    "    def testBaseCaseZeroLength(self):\n",
    "        self.assertEqual(lis([]), [])\n",
    "        \n",
    "    def testBaseCaseOneLength(self):\n",
    "        self.assertEqual(lis([1]), [1])\n",
    "\n",
    "    def testSimpleAscending(self):\n",
    "        self.assertEqual(lis([1, 2]), [1, 2])\n",
    "\n",
    "    def testLongerAscending(self):\n",
    "        self.assertEqual(lis([1, 2, 3, 4, 5, 6]), [1, 2, 3, 4, 5, 6])        \n",
    "        \n",
    "    def testNonMonotonic(self):\n",
    "        self.assertEqual(len(lis([1, 5, 2, 6, 3, 7])), 4)        \n",
    "        \n",
    "        \n",
    "if __name__ == '__main__':\n",
    "    unittest.main(argv=[''], exit=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def lis(seq, result=[], prior_subseq=[], prior_subseq_idx=[]):\n",
    "    \n",
    "    if len(seq) == 0: return []\n",
    "    if len(seq) == 1: return seq\n",
    "    \n",
    "    if prior_subseq and prior_subseq_idx:\n",
    "        prior_max, prior_max_idx = prior_subseq[-1], prior_subseq_idx[-1]\n",
    "    else:\n",
    "        prior_subseq, prior_subseq_idx = [seq[0]], [0]\n",
    "        prior_max, prior_max_idx = seq[0], 0\n",
    "    \n",
    "    remaining_subseq_idx_start = prior_max_idx + 1\n",
    "    remaining_subseq = seq[remaining_subseq_idx_start:]\n",
    "    remaining_seq_idx = [i + remaining_subseq_idx_start for (i, v) in enumerate(remaining_subseq) if v > prior_max]\n",
    "    \n",
    "    for idx in remaining_seq_idx:\n",
    "        potential_result = lis(seq, prior_subseq + [seq[idx]], prior_subseq + [seq[idx]], prior_subseq_idx + [idx])\n",
    "        if len(potential_result) > len(result):\n",
    "            result = potential_result\n",
    "    \n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Property analysis\n",
    "\n",
    "Done on a piece of paper. The major properties are that you can collect cases by iterating leftwards, and that you can cut down on the number of comparisons you have to make to collect new subsequences using some kind of ordered-access memory structure (simple: a list whose indices correspond with first values in the subsequence)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Optimized pseudocode\n",
    "\n",
    "```\n",
    "function lis(s):\n",
    "    store = [[] for n in range(max(s))]\n",
    "    for v in s[::-1]:\n",
    "        for v_slot in store[v:]:\n",
    "            for l in v_slot:\n",
    "                l.prepend(v)\n",
    "                \n",
    "        if not store[v]:\n",
    "            store[v] = [v]\n",
    "\n",
    "    return longest_element(store)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Optimized implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "def lis(s):\n",
    "    if len(s) == 0: return []\n",
    "    \n",
    "    store = [[] for _ in range(max(s) + 1)]\n",
    "    for v in s[::-1]:\n",
    "        for v_slot in store[v + 1:]:\n",
    "            for l in v_slot:\n",
    "                store[v].append([v] + l)\n",
    "                \n",
    "        if not store[v]:\n",
    "            store[v] = [[v]]\n",
    "    \n",
    "    macro_order = sorted(store, key=lambda l: max([len(li) for li in l]) if l else 0)\n",
    "    return sorted(macro_order[-1], key=lambda l: len(l))[-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The brute force solution is $O(n!)$, with a worst case of a completely sorted list. The optimized solution is $O(n^3)$."
   ]
  }
 ],
 "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.6.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}