Dynamic Programming/Longest_Increasing_Subsequence.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Longest_Increasing_Subsequence.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "metadata": {
        "id": "a3hYgaHPUkua"
      },
      "source": [
        "'''\n",
        "  Function to find Longest Increasing/Decreasing Subsequence of an array based on patience sorting\n",
        "  Time complexity = O(n.log(n))\n",
        "\n",
        "  Parameters:\n",
        "  -----------\n",
        "    arr     : list\n",
        "              Input array of numbers\n",
        "    algoType: 'LIS' (by default) or 'LDS', optional\n",
        "              Algorithm type: Longest Increasing Subsequence (LIS)\n",
        "              or Longest Decreasing Subsequence (LDS)\n",
        "\n",
        "  Returns:\n",
        "  --------\n",
        "    result: tuple\n",
        "            A tuple of length of LIS, LIS and its indices in input array\n",
        "            or length of LDS, LDS and its indices in input array\n",
        "\n",
        "  Examples:\n",
        "  ---------\n",
        "      Given an array list: \n",
        "                          2  5  3  7  11  8  10  13  6\n",
        "      LIS of this array is: \n",
        "                         [2] 5 [3] [7] 11 [8] [10] [13] 6    => 6 elements\n",
        "      Its position is:  \n",
        "                          0     2   3      5   6    7\n",
        "\n",
        "    >>> arr = [2, 5, 3, 7, 11, 8, 10, 13, 6] \n",
        "    >>> print(Longest_Increasing_Subsequence(arr))\n",
        "    (6, [2, 3, 7, 8, 10, 13], [0, 2, 3, 5, 6, 7])\n",
        "\n",
        "    >>> print(Longest_Increasing_Subsequence(arr, algoType='LDS'))\n",
        "    (3, [11, 8, 6], [4, 5, 8])\n",
        "\n",
        "  References:\n",
        "    https://www.youtube.com/watch?v=S9oUiVYEq7E\n",
        "    https://www.youtube.com/watch?v=22s1xxRvy28&feature=youtu.be\n",
        "    https://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/\n",
        "'''\n",
        "   \n",
        "def Longest_Increasing_Subsequence(arr, algoType='LIS'):  \n",
        "  # Convert input for algorithm type: Longest Increasing Subsequence (LIS) or Longest Decreasing Subsequence (LDS)\n",
        "  if algoType == 'LIS': \n",
        "    pass\n",
        "  elif algoType == 'LDS': \n",
        "    arr = arr[::-1]\n",
        "\n",
        "  # Modified binary search \n",
        "  def GetCeilIndex(arr, T, l, r, key): \n",
        "    while r - l > 1: \n",
        "      m = l + (r - l)//2\n",
        "      if arr[T[m]] >= key: \n",
        "        r = m \n",
        "      else: \n",
        "        l = m \n",
        "    return r   \n",
        "\n",
        "  # Initialized with 0 \n",
        "  tailIndices =[0 for i in range(len(arr)+1)]    \n",
        "  # Initialized with -1 \n",
        "  prevIndices =[-1 for i in range(len(arr)+1)]   \n",
        "      \n",
        "  # It will always point to empty location \n",
        "  length = 1 \n",
        "  for i in range(1, len(arr)):      \n",
        "    if arr[i] < arr[tailIndices[0]]:          \n",
        "      # New smallest value \n",
        "      tailIndices[0] = i \n",
        "\n",
        "    elif arr[i] >= arr[tailIndices[length-1]]:           \n",
        "      # arr[i] wants to extend largest subsequence \n",
        "      prevIndices[i] = tailIndices[length-1] \n",
        "      tailIndices[length] = i \n",
        "      length += 1\n",
        "          \n",
        "    else: \n",
        "      # arr[i] wants to be a potential condidate of future subsequence \n",
        "      # It will replace ceil value in tailIndices \n",
        "      pos = GetCeilIndex(arr, tailIndices, -1, length-1, arr[i]) \n",
        "      prevIndices[i] = tailIndices[pos-1] \n",
        "      tailIndices[pos] = i \n",
        "          \n",
        "  # Construct Longest Increasing Subsequence and its indices \n",
        "  if algoType == 'LIS':\n",
        "    LIS = []\n",
        "    LIS_idx = []\n",
        "    i = tailIndices[length-1]\n",
        "\n",
        "    while i >= 0: \n",
        "      LIS.insert(0,arr[i])\n",
        "      LIS_idx.insert(0,i)\n",
        "      i = prevIndices[i] \n",
        "\n",
        "    result = (length, LIS, LIS_idx)\n",
        "\n",
        "  # Construct Longest Decreasing Subsequence and its indices\n",
        "  elif algoType == 'LDS':\n",
        "    LDS = []\n",
        "    LDS_idx = []\n",
        "    i = tailIndices[length-1]\n",
        "\n",
        "    while i >= 0: \n",
        "      LDS.append(arr[i])\n",
        "      LDS_idx.append(len(arr)-1-i)\n",
        "      i = prevIndices[i] \n",
        "\n",
        "    result = (length, LDS, LDS_idx)\n",
        "\n",
        "  return result"
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}