algorithms/300-longest-increasing-subsequence.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "precious-perth",
   "metadata": {},
   "source": [
    "### [最长递增子序列](https://leetcode-cn.com/problems/longest-increasing-subsequence/)\n",
    "\n",
    "给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。\n",
    "\n",
    "子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。\n",
    "\n",
    "#### 示例 1：\n",
    "```\n",
    "输入：nums = [10,9,2,5,3,7,101,18]\n",
    "输出：4\n",
    "解释：最长递增子序列是 [2,3,7,101]，因此长度为 4\n",
    "```\n",
    "\n",
    "示例 2：\n",
    "```\n",
    "输入：nums = [0,1,0,3,2,3]\n",
    "输出：4\n",
    "```\n",
    "\n",
    "#### 示例 3：\n",
    "```\n",
    "输入：nums = [7,7,7,7,7,7,7]\n",
    "输出：1\n",
    "```\n",
    "\n",
    "#### 提示：\n",
    "- `1 <= nums.length <= 2500`\n",
    "- `-104 <= nums[i] <= 104`\n",
    "\n",
    "#### 进阶：\n",
    "\n",
    "- 你可以设计时间复杂度为`O(n2)`的解决方案吗？\n",
    "- 你能将算法的时间复杂度降低到`O(nlog(n))`吗?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "loaded-saint",
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "\n",
    "def lengthOfLIS(nums: List[int]) -> int:\n",
    "    n = len(nums)\n",
    "    if n < 2:\n",
    "        return n\n",
    "    \n",
    "    dp = [1 for _ in range(n)]\n",
    "    for i in range(1, n):\n",
    "        for j in range(i):\n",
    "            if nums[j] < nums[i]:\n",
    "                dp[i] = max(dp[j] + 1, dp[i])\n",
    "    \n",
    "    return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "accepted-murder",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lengthOfLIS([2,1,5,3,6,4,8,9,7])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "taken-terminal",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lengthOfLIS([1,2,8,6,4])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "capital-vienna",
   "metadata": {},
   "source": [
    "给定数组arr，设长度为n，输出arr的最长递增子序列。（如果有多个答案，请输出其中字典序最小的）\n",
    "\n",
    "#### 示例1\n",
    "```\n",
    "输入 [2,1,5,3,6,4,8,9,7]\n",
    "返回值 [1,3,4,8,9]\n",
    "```\n",
    "\n",
    "#### 示例2\n",
    "```\n",
    "输入 [1,2,8,6,4]\n",
    "返回值 [1,2,4]\n",
    "```\n",
    "\n",
    "#### 说明\n",
    "\n",
    "其最长递增子序列有3个，（1，2，8）、（1，2，6）、（1，2，4）其中第三个字典序最小，故答案为（1，2，4）\n",
    "\n",
    "#### 备注:\n",
    "\n",
    "- $ n \\leq 10^5 $\n",
    "- $ 1 \\leq arr_i \\leq 10^9 $"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "id": "attractive-photography",
   "metadata": {},
   "outputs": [],
   "source": [
    "def lis(arr: List[int]) -> List[int]:\n",
    "    n = len(arr)\n",
    "    if n < 2:\n",
    "        return arr\n",
    "    \n",
    "    dp = [[[arr[i]]] for i in range(n)]\n",
    "    for i in range(1, n):\n",
    "        for j in range(i):\n",
    "            if arr[j] < arr[i]:\n",
    "                for path in dp[j]:\n",
    "                    newPath = path.copy()\n",
    "                    newPath.append(arr[i])\n",
    "                    dp[i].append(newPath)\n",
    "    ans = []\n",
    "    for paths in dp:\n",
    "        ans.extend(paths)\n",
    "        del paths\n",
    "    dp.clear()\n",
    "    ans.sort(key=lambda a: (len(a), -a[0]))\n",
    "    return ans[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "id": "functional-banana",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 4]"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lts([1,2,8,6,4])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "id": "prepared-sequence",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 3, 4, 8, 9]"
      ]
     },
     "execution_count": 88,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lts([2,1,5,3,6,4,8,9,7])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "id": "valued-hindu",
   "metadata": {},
   "outputs": [],
   "source": [
    "def findLIS(arr: List[int]) -> List[int]:\n",
    "    \n",
    "    def featuresOfLIS(nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        if n < 2:\n",
    "            return nums\n",
    "\n",
    "        dp = [1] * n\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if nums[i] > nums[j]:\n",
    "                    dp[i] = max(dp[j] + 1, dp[i])\n",
    "        return dp\n",
    "    \n",
    "    def generateLIS(nums: List[int], dp: List[int]) -> List[int]:\n",
    "        n, idx, l = len(nums), 0, dp[0]\n",
    "        for i in range(1, n):\n",
    "            if dp[i] > dp[idx]:\n",
    "                idx, l = i, dp[i]\n",
    "        \n",
    "        lis = [0 for i in range(l)]\n",
    "        l -= 1\n",
    "        lis[l] = nums[idx]\n",
    "        \n",
    "        for i in reversed(range(idx)):\n",
    "            if nums[i] < nums[idx] and dp[i] == dp[idx] - 1:\n",
    "                l -= 1\n",
    "                lis[l] = nums[i]\n",
    "                idx = i\n",
    "        return lis\n",
    "    \n",
    "    dp = featuresOfLIS(arr)\n",
    "    return generateLIS(arr, dp)  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 125,
   "id": "quiet-accounting",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 3, 4, 8, 9]"
      ]
     },
     "execution_count": 125,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "findLIS([2,1,5,3,6,4,8,9,7])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 126,
   "id": "southwest-trance",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 8]"
      ]
     },
     "execution_count": 126,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "findLIS([1,2,8,6,4])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 127,
   "id": "selected-necklace",
   "metadata": {},
   "outputs": [],
   "source": [
    "def findLIS(arr: List[int]) -> List[int]:\n",
    "    \n",
    "    def featuresOfLIS(nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        if n < 2:\n",
    "            return nums\n",
    "\n",
    "        dp = [1] * n\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if nums[i] > nums[j]:\n",
    "                    dp[i] = max(dp[j] + 1, dp[i])\n",
    "        return dp\n",
    "    \n",
    "    def generateLIS(nums: List[int], dp: List[int]) -> List[int]:\n",
    "        n, idx, l = len(nums), 0, dp[0]\n",
    "        for i in range(1, n):\n",
    "            if dp[i] > dp[idx]:\n",
    "                idx, l = i, dp[i]\n",
    "            elif dp[i] == dp[idx]:\n",
    "                if nums[i] < nums[idx]:\n",
    "                    idx, l = i, dp[i]\n",
    "        \n",
    "        lis = [0 for i in range(l)]\n",
    "        l -= 1\n",
    "        lis[l] = nums[idx]\n",
    "        \n",
    "        for i in reversed(range(idx)):\n",
    "            if nums[i] < nums[idx] and dp[i] == dp[idx] - 1:\n",
    "                l -= 1\n",
    "                lis[l] = nums[i]\n",
    "                idx = i\n",
    "        return lis\n",
    "    \n",
    "    dp = featuresOfLIS(arr)\n",
    "    return generateLIS(arr, dp) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 128,
   "id": "expressed-policy",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 3, 4, 8, 9]"
      ]
     },
     "execution_count": 128,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "findLIS([2,1,5,3,6,4,8,9,7])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 129,
   "id": "precise-lindsay",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 4]"
      ]
     },
     "execution_count": 129,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "findLIS([1,2,8,6,4])"
   ]
  }
 ],
 "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.8.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}