{"id":6536,"date":"2024-01-08T21:59:52","date_gmt":"2024-01-08T13:59:52","guid":{"rendered":"https:\/\/zyrastory.com\/?p=6536"},"modified":"2024-02-20T15:31:28","modified_gmt":"2024-02-20T07:31:28","slug":"leetcode-300-longest-increasing-subsequence-solution-and-explanation-en","status":"publish","type":"post","link":"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/","title":{"rendered":"LeetCode #300\u00a0Longest Increasing Subsequence Solution &#038; Explanation"},"content":{"rendered":"<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_65 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title \" >\u5167\u5bb9\u76ee\u9304<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/#leetcode-problem\" title=\"LeetCode Problem\">LeetCode Problem<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/#solution\" title=\"Solution\">Solution<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/#c-solution\" title=\"C# Solution\">C# Solution<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/#java-solution\" title=\"Java Solution\">Java Solution<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/#python3-solution\" title=\"Python3 Solution\">Python3 Solution<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/#javascript-solution\" title=\"JavaScript Solution\">JavaScript Solution<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/#conclusion\" title=\"Conclusion\">Conclusion<\/a><\/li><\/ul><\/nav><\/div>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"leetcode-problem\"><\/span><strong>LeetCode Problem<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>Given an integer array&nbsp;<strong>nums<\/strong>, return&nbsp;<em>the length of the longest&nbsp;<strong>strictly increasing<\/strong><\/em> <em><strong>subsequence<\/strong><\/em>.<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p><\/p>\n<cite>A&nbsp;<strong>subsequence<\/strong>&nbsp;is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.<\/cite><\/blockquote>\n\n\n\n<div style=\"height:25px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"721\" height=\"715\" src=\"https:\/\/zyrastory.com\/wp-content\/uploads\/2024\/01\/300_Examples_Constraints.webp\" alt=\"\" class=\"wp-image-6541\" srcset=\"https:\/\/zyrastory.com\/wp-content\/uploads\/2024\/01\/300_Examples_Constraints.webp 721w, https:\/\/zyrastory.com\/wp-content\/uploads\/2024\/01\/300_Examples_Constraints-300x298.webp 300w, https:\/\/zyrastory.com\/wp-content\/uploads\/2024\/01\/300_Examples_Constraints-150x150.webp 150w\" sizes=\"(max-width: 721px) 100vw, 721px\" \/><\/figure>\n\n\n\n<p><strong>Follow up:<\/strong>&nbsp;Can you come up with an algorithm that runs in&nbsp;<strong>O(n log(n))<\/strong>&nbsp;time complexity?<\/p>\n\n\n\n<div style=\"height:25px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"solution\"><\/span><strong>Solution<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<div style=\"height:30px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"c-solution\"><\/span><strong>C# Solution<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p><strong>Solution1<\/strong><\/p>\n\n\n\n<div class=\"hcb_wrap\"><pre class=\"prism undefined-numbers lang-csharp\" data-lang=\"C#\"><code>public class Solution {\n    public int LengthOfLIS(int[] nums) {\n\n        int[]arr = new int[nums.Length];\n        Array.Fill(arr, 1);\n\n        for(int i=1;i&lt;nums.Length;i++){\n            for(int j=0;j&lt;i;j++){\n                if (nums[i] &gt; nums[j])\n                {\n                    arr[i] = Math.Max(arr[i], arr[j] + 1);\n                }\n            }        \n        }\n        return arr.Max();\n    }\n}<\/code><\/pre><\/div>\n\n\n\n<p><strong>Time Complexity : O(n<sup>2<\/sup>)<\/strong><\/p>\n\n\n\n<p>In summary, this code uses dynamic programming to find the length of the longest increasing subsequence in an array of integers. The <strong>arr <\/strong>array is used to store the length of the longest increasing subsequence ending at each index.<\/p>\n\n\n\n<p><strong><em>Array.Fill(arr, 1);<\/em><\/strong>  \u27a1  Initially, each individual element in the array is treated as a subsequence of length 1.<\/p>\n\n\n\n<p><strong><em>for (int i = 1; i &lt; nums.Length; i++)<\/em><\/strong> and for <strong><em>(int j = 0; j &lt; i; j++)<\/em><\/strong>  \u27a1 is used to iterate through all combinations of elements. Here, i represents the current element, and j represents the elements before the current one.<\/p>\n\n\n\n<p><strong><em>arr[i] = Math.Max(arr[i], arr[j] + 1); <\/em><\/strong>\u27a1 represents the dynamic programming update. It ensures that the length of the longest increasing subsequence ending at index i is updated to the maximum of its current value arr[i] and the length of the subsequence ending at j plus one (arr[j] + 1). <\/p>\n\n\n\n<div style=\"height:45px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"java-solution\"><\/span><strong>Java Solution<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p><strong>Solution1<\/strong><\/p>\n\n\n\n<div class=\"hcb_wrap\"><pre class=\"prism undefined-numbers lang-java\" data-lang=\"Java\"><code>class Solution {\n    public int lengthOfLIS(int[] nums) {\n        int[]arr = new int[nums.length];\n        \n        for (int i = 0; i &lt; arr.length; i++) {\n            arr[i] = 1;\n        }\n\n        for(int i=1;i&lt;nums.length;i++){\n            for(int j=0;j&lt;i;j++){\n                if (nums[i] &gt; nums[j])\n                {\n                    arr[i] = Math.max(arr[i], arr[j] + 1);\n                }\n            }        \n        }\n        return Arrays.stream(arr).max().orElse(0);\n    }\n}<\/code><\/pre><\/div>\n\n\n\n<p><strong>Time Complexity : O(n<sup>2<\/sup>)<\/strong><\/p>\n\n\n\n<p>The Java Stream <strong>max()<\/strong> method returns an <strong>OptionalInt<\/strong>, so you need to use <strong>orElse<\/strong> to convert it to an integer.<\/p>\n\n\n\n<div style=\"height:45px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"python3-solution\"><\/span><strong>Python3 Solution<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p><strong>Solution1<\/strong><\/p>\n\n\n\n<div class=\"hcb_wrap\"><pre class=\"prism undefined-numbers lang-python\" data-lang=\"Python\"><code>class Solution:\n    def lengthOfLIS(self, nums: List[int]) -&gt; int:\n        arr = [1] * len(nums)\n\n        for i in range(1, len(nums)):\n            for j in range(i):\n                if nums[i] &gt; nums[j]:\n                    arr[i] = max(arr[i], arr[j] + 1)\n\n        return max(arr)<\/code><\/pre><\/div>\n\n\n\n<div style=\"height:45px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"javascript-solution\"><\/span><strong>JavaScript Solution<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p><strong>Solution1<\/strong><\/p>\n\n\n\n<div class=\"hcb_wrap\"><pre class=\"prism undefined-numbers lang-js\" data-lang=\"JavaScript\"><code>\/**\n * @param {number[]} nums\n * @return {number}\n *\/\nvar lengthOfLIS = function(nums) {\n    var arr = Array(nums.length).fill(1);\n\n        for(let i=1;i&lt;nums.length;i++){\n            for(let j=0;j&lt;i;j++){\n                if (nums[i] &gt; nums[j])\n                {\n                    arr[i] = Math.max(arr[i], arr[j] + 1);\n                }\n            }        \n        }\n\n        return (Math.max(...arr));\n};<\/code><\/pre><\/div>\n\n\n\n<div style=\"height:30px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"tw-target-text\"><span class=\"ez-toc-section\" id=\"conclusion\"><\/span><strong>Conclusion<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>The current approach I can think of is <strong>O(n<sup>2<\/sup>)<\/strong>, but the follow-up of the problem suggests there might be a solution in <strong>O(n log(n))<\/strong>. Let me take some time to think about it, and I will provide an update later.<\/p>\n\n\n\n<p>P.S. Dynamic programming problems always seem challenging&#8230;<\/p>\n\n\n\n<div style=\"height:45px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<p class=\"has-medium-font-size\">\ud83e\udde1<strong>If my solution helps, that is my honor!<\/strong><\/p>\n\n\n\n<p>\ud83e\udde1<strong>You can support me by  sharing my posts, thanks a lot<\/strong><\/p>\n\n\n\n<p>\u2705<strong>If you got any problem about the explanation, please feel free to let me know<\/strong><\/p>\n\n\n\n<div style=\"height:30px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<p><strong>The problem link :<\/strong> <a href=\"https:\/\/leetcode.com\/problems\/longest-increasing-subsequence\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\">Longest Increasing Subsequence &#8211; LeetCode<\/a><\/p>\n\n\n\n<div style=\"height:40px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<p><strong>Some Random LeetCode posts<\/strong><\/p>\n\n\n\n\t\t\t<div class=\"wp-block-uagb-post-grid uagb-post-grid  uagb-post__image-position-top uagb-post__image-disabled uagb-block-f4bc3f3d     uagb-post__items uagb-post__columns-3 is-grid uagb-post__columns-tablet-2 uagb-post__columns-mobile-1 uagb-post__equal-height\" data-total=\"13\" style=\"\">\n\n\t\t\t\t\t\t\t\t\t\t\t\t<article class=\"uagb-post__inner-wrap\">\t\t\t\t\t\t\t\t<h4 class=\"uagb-post__title uagb-post__text\">\n\t\t\t\t<a href=\"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-1544-make-the-string-great-solution-and-explanation-en\/\" target=\"_self\" rel=\"bookmark noopener noreferrer\">LeetCode #1544 Make The String Great Solution &amp; Explanation<\/a>\n\t\t\t<\/h4>\n\t\t\t\t\t\t<div class='uagb-post__text uagb-post-grid-byline'>\n\t\t\t\t\t\t\t\t<time datetime=\"2024-04-07T15:40:06+08:00\" class=\"uagb-post__date\">\n\t\t\t\t<span class=\"dashicons-calendar dashicons\"><\/span>\t\t\t\t\t2024-04-07\t\t\t\t<\/time>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<div class=\"uagb-post__text uagb-post__cta wp-block-button\">\n\t\t\t\t<a class=\"wp-block-button__link uagb-text-link\" href=\"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-1544-make-the-string-great-solution-and-explanation-en\/\" target=\"_self\" rel=\"bookmark noopener noreferrer\">Read More<\/a>\n\t\t\t<\/div>\n\t\t\t\t\t\t\t\t\t\t\t\t<\/article>\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<article class=\"uagb-post__inner-wrap\">\t\t\t\t\t\t\t\t<h4 class=\"uagb-post__title uagb-post__text\">\n\t\t\t\t<a href=\"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-977-squares-of-a-sorted-array-solution-and-explanation-en\/\" target=\"_self\" rel=\"bookmark noopener noreferrer\">LeetCode #977 Squares of a Sorted Array Solution &#038; Explanation<\/a>\n\t\t\t<\/h4>\n\t\t\t\t\t\t<div class='uagb-post__text uagb-post-grid-byline'>\n\t\t\t\t\t\t\t\t<time datetime=\"2024-03-20T22:43:12+08:00\" class=\"uagb-post__date\">\n\t\t\t\t<span class=\"dashicons-calendar dashicons\"><\/span>\t\t\t\t\t2024-03-20\t\t\t\t<\/time>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<div class=\"uagb-post__text uagb-post__cta wp-block-button\">\n\t\t\t\t<a class=\"wp-block-button__link uagb-text-link\" href=\"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-977-squares-of-a-sorted-array-solution-and-explanation-en\/\" target=\"_self\" rel=\"bookmark noopener noreferrer\">Read More<\/a>\n\t\t\t<\/div>\n\t\t\t\t\t\t\t\t\t\t\t\t<\/article>\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<article class=\"uagb-post__inner-wrap\">\t\t\t\t\t\t\t\t<h4 class=\"uagb-post__title uagb-post__text\">\n\t\t\t\t<a href=\"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-290-word-pattern-solution-and-explanation-en\/\" target=\"_self\" rel=\"bookmark noopener noreferrer\">LeetCode #290\u00a0Word Pattern Solution &#038; Explanation<\/a>\n\t\t\t<\/h4>\n\t\t\t\t\t\t<div class='uagb-post__text uagb-post-grid-byline'>\n\t\t\t\t\t\t\t\t<time datetime=\"2023-08-27T23:49:48+08:00\" class=\"uagb-post__date\">\n\t\t\t\t<span class=\"dashicons-calendar dashicons\"><\/span>\t\t\t\t\t2023-08-27\t\t\t\t<\/time>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<div class=\"uagb-post__text uagb-post__cta wp-block-button\">\n\t\t\t\t<a class=\"wp-block-button__link uagb-text-link\" href=\"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-290-word-pattern-solution-and-explanation-en\/\" target=\"_self\" rel=\"bookmark noopener noreferrer\">Read More<\/a>\n\t\t\t<\/div>\n\t\t\t\t\t\t\t\t\t\t\t\t<\/article>\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<article class=\"uagb-post__inner-wrap\">\t\t\t\t\t\t\t\t<h4 class=\"uagb-post__title uagb-post__text\">\n\t\t\t\t<a href=\"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-28-find-the-index-of-the-first-occurrence-in-a-string-solution-and-explanation-en\/\" target=\"_self\" rel=\"bookmark noopener noreferrer\">LeetCode #28\u00a0Find the Index of the First Occurrence in a String Solution &#038; Explanation<\/a>\n\t\t\t<\/h4>\n\t\t\t\t\t\t<div class='uagb-post__text uagb-post-grid-byline'>\n\t\t\t\t\t\t\t\t<time datetime=\"2022-10-26T17:33:43+08:00\" class=\"uagb-post__date\">\n\t\t\t\t<span class=\"dashicons-calendar dashicons\"><\/span>\t\t\t\t\t2022-10-26\t\t\t\t<\/time>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<div class=\"uagb-post__text uagb-post__cta wp-block-button\">\n\t\t\t\t<a class=\"wp-block-button__link uagb-text-link\" href=\"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-28-find-the-index-of-the-first-occurrence-in-a-string-solution-and-explanation-en\/\" target=\"_self\" rel=\"bookmark noopener noreferrer\">Read More<\/a>\n\t\t\t<\/div>\n\t\t\t\t\t\t\t\t\t\t\t\t<\/article>\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<article class=\"uagb-post__inner-wrap\">\t\t\t\t\t\t\t\t<h4 class=\"uagb-post__title uagb-post__text\">\n\t\t\t\t<a href=\"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-205-isomorphic-strings-solution-and-explanation-en\/\" target=\"_self\" rel=\"bookmark noopener noreferrer\">LeetCode #205\u00a0Isomorphic Strings Solution &#038; Explanation<\/a>\n\t\t\t<\/h4>\n\t\t\t\t\t\t<div class='uagb-post__text uagb-post-grid-byline'>\n\t\t\t\t\t\t\t\t<time datetime=\"2023-09-11T23:22:12+08:00\" class=\"uagb-post__date\">\n\t\t\t\t<span class=\"dashicons-calendar dashicons\"><\/span>\t\t\t\t\t2023-09-11\t\t\t\t<\/time>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<div class=\"uagb-post__text uagb-post__cta wp-block-button\">\n\t\t\t\t<a class=\"wp-block-button__link uagb-text-link\" href=\"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-205-isomorphic-strings-solution-and-explanation-en\/\" target=\"_self\" rel=\"bookmark noopener noreferrer\">Read More<\/a>\n\t\t\t<\/div>\n\t\t\t\t\t\t\t\t\t\t\t\t<\/article>\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<article class=\"uagb-post__inner-wrap\">\t\t\t\t\t\t\t\t<h4 class=\"uagb-post__title uagb-post__text\">\n\t\t\t\t<a href=\"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-1338-reduce-array-size-to-the-half-solution-and-explanation-en\/\" target=\"_self\" rel=\"bookmark noopener noreferrer\">LeetCode #1338\u00a0Reduce Array Size to The Half Solution &#038; Explanation<\/a>\n\t\t\t<\/h4>\n\t\t\t\t\t\t<div class='uagb-post__text uagb-post-grid-byline'>\n\t\t\t\t\t\t\t\t<time datetime=\"2022-08-29T17:56:31+08:00\" class=\"uagb-post__date\">\n\t\t\t\t<span class=\"dashicons-calendar dashicons\"><\/span>\t\t\t\t\t2022-08-29\t\t\t\t<\/time>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<div class=\"uagb-post__text uagb-post__cta wp-block-button\">\n\t\t\t\t<a class=\"wp-block-button__link uagb-text-link\" href=\"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-1338-reduce-array-size-to-the-half-solution-and-explanation-en\/\" target=\"_self\" rel=\"bookmark noopener noreferrer\">Read More<\/a>\n\t\t\t<\/div>\n\t\t\t\t\t\t\t\t\t\t\t\t<\/article>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<div class=\"uagb-post-pagination-wrap\">\n\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t","protected":false},"excerpt":{"rendered":"<p>This is a classic dynamic programming problem, return\u00a0the length of the longest\u00a0increasing subsequence.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_uag_custom_page_level_css":"","footnotes":""},"categories":[62],"tags":[182,84,78,79,91,82],"blocksy_meta":[],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v22.6 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>LeetCode #300\u00a0Longest Increasing Subsequence Solution &amp; Explanation - zyrastory\u7a0b\u5f0f\u7f8e\u98df\u7814\u7a76\u4e2d\u5fc3<\/title>\n<meta name=\"description\" content=\"This is a classic dynamic programming problem, return\u00a0the length of the longest\u00a0increasing subsequence. C#, Java, Python3, JS solution\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/\" \/>\n<meta property=\"og:locale\" content=\"zh_TW\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"LeetCode #300\u00a0Longest Increasing Subsequence Solution &amp; Explanation - zyrastory\u7a0b\u5f0f\u7f8e\u98df\u7814\u7a76\u4e2d\u5fc3\" \/>\n<meta property=\"og:description\" content=\"This is a classic dynamic programming problem, return\u00a0the length of the longest\u00a0increasing subsequence. C#, Java, Python3, JS solution\" \/>\n<meta property=\"og:url\" content=\"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/\" \/>\n<meta property=\"og:site_name\" content=\"zyrastory\u7a0b\u5f0f\u7f8e\u98df\u7814\u7a76\u4e2d\u5fc3\" \/>\n<meta property=\"article:published_time\" content=\"2024-01-08T13:59:52+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-02-20T07:31:28+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/zyrastory.com\/wp-content\/uploads\/2024\/01\/300_Examples_Constraints.webp\" \/>\n<meta name=\"author\" content=\"zyrastory\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"\u4f5c\u8005:\" \/>\n\t<meta name=\"twitter:data1\" content=\"zyrastory\" \/>\n\t<meta name=\"twitter:label2\" content=\"\u9810\u4f30\u95b1\u8b80\u6642\u9593\" \/>\n\t<meta name=\"twitter:data2\" content=\"3 \u5206\u9418\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/\"},\"author\":{\"name\":\"zyrastory\",\"@id\":\"https:\/\/zyrastory.com\/#\/schema\/person\/0d3b4bc5302f8e3dd68cbb6464b888dd\"},\"headline\":\"LeetCode #300\u00a0Longest Increasing Subsequence Solution &#038; Explanation\",\"datePublished\":\"2024-01-08T13:59:52+00:00\",\"dateModified\":\"2024-02-20T07:31:28+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/\"},\"wordCount\":360,\"commentCount\":0,\"publisher\":{\"@id\":\"https:\/\/zyrastory.com\/#\/schema\/person\/0d3b4bc5302f8e3dd68cbb6464b888dd\"},\"image\":{\"@id\":\"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/zyrastory.com\/wp-content\/uploads\/2024\/01\/300_Examples_Constraints.webp\",\"keywords\":[\"Blind 75\",\"LeetCode C#Solution\",\"LeetCode Java Solution\",\"LeetCode JavaScript Solution\",\"LeetCode Medium\",\"LeetCode Python3 Solution\"],\"articleSection\":[\"LeetCode Solution\"],\"inLanguage\":\"zh-TW\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/\",\"url\":\"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/\",\"name\":\"LeetCode #300\u00a0Longest Increasing Subsequence Solution & Explanation - zyrastory\u7a0b\u5f0f\u7f8e\u98df\u7814\u7a76\u4e2d\u5fc3\",\"isPartOf\":{\"@id\":\"https:\/\/zyrastory.com\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/zyrastory.com\/wp-content\/uploads\/2024\/01\/300_Examples_Constraints.webp\",\"datePublished\":\"2024-01-08T13:59:52+00:00\",\"dateModified\":\"2024-02-20T07:31:28+00:00\",\"description\":\"This is a classic dynamic programming problem, return\u00a0the length of the longest\u00a0increasing subsequence. C#, Java, Python3, JS solution\",\"breadcrumb\":{\"@id\":\"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/#breadcrumb\"},\"inLanguage\":\"zh-TW\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"zh-TW\",\"@id\":\"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/#primaryimage\",\"url\":\"https:\/\/zyrastory.com\/wp-content\/uploads\/2024\/01\/300_Examples_Constraints.webp\",\"contentUrl\":\"https:\/\/zyrastory.com\/wp-content\/uploads\/2024\/01\/300_Examples_Constraints.webp\",\"width\":721,\"height\":715},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\u9996\u9801\",\"item\":\"https:\/\/zyrastory.com\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"LeetCode #300\u00a0Longest Increasing Subsequence Solution &#038; Explanation\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/zyrastory.com\/#website\",\"url\":\"https:\/\/zyrastory.com\/\",\"name\":\"zyrastory\u7a0b\u5f0f\u7f8e\u98df\u7814\u7a76\u4e2d\u5fc3\",\"description\":\"\u53ea\u662f\u500b\u559c\u6b61\u5206\u4eab\u7684\u5c0f\u5de5\u7a0b\u5e2b\",\"publisher\":{\"@id\":\"https:\/\/zyrastory.com\/#\/schema\/person\/0d3b4bc5302f8e3dd68cbb6464b888dd\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/zyrastory.com\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"zh-TW\"},{\"@type\":[\"Person\",\"Organization\"],\"@id\":\"https:\/\/zyrastory.com\/#\/schema\/person\/0d3b4bc5302f8e3dd68cbb6464b888dd\",\"name\":\"zyrastory\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"zh-TW\",\"@id\":\"https:\/\/zyrastory.com\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/c0f3eeb72ed82297486aa0323b8a29fb?s=96&d=identicon&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/c0f3eeb72ed82297486aa0323b8a29fb?s=96&d=identicon&r=g\",\"caption\":\"zyrastory\"},\"logo\":{\"@id\":\"https:\/\/zyrastory.com\/#\/schema\/person\/image\/\"},\"sameAs\":[\"https:\/\/zyrastory.com\"],\"url\":\"https:\/\/zyrastory.com\/author\/zyrastory\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"LeetCode #300\u00a0Longest Increasing Subsequence Solution & Explanation - zyrastory\u7a0b\u5f0f\u7f8e\u98df\u7814\u7a76\u4e2d\u5fc3","description":"This is a classic dynamic programming problem, return\u00a0the length of the longest\u00a0increasing subsequence. C#, Java, Python3, JS solution","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/","og_locale":"zh_TW","og_type":"article","og_title":"LeetCode #300\u00a0Longest Increasing Subsequence Solution & Explanation - zyrastory\u7a0b\u5f0f\u7f8e\u98df\u7814\u7a76\u4e2d\u5fc3","og_description":"This is a classic dynamic programming problem, return\u00a0the length of the longest\u00a0increasing subsequence. C#, Java, Python3, JS solution","og_url":"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/","og_site_name":"zyrastory\u7a0b\u5f0f\u7f8e\u98df\u7814\u7a76\u4e2d\u5fc3","article_published_time":"2024-01-08T13:59:52+00:00","article_modified_time":"2024-02-20T07:31:28+00:00","og_image":[{"url":"https:\/\/zyrastory.com\/wp-content\/uploads\/2024\/01\/300_Examples_Constraints.webp"}],"author":"zyrastory","twitter_card":"summary_large_image","twitter_misc":{"\u4f5c\u8005:":"zyrastory","\u9810\u4f30\u95b1\u8b80\u6642\u9593":"3 \u5206\u9418"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/#article","isPartOf":{"@id":"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/"},"author":{"name":"zyrastory","@id":"https:\/\/zyrastory.com\/#\/schema\/person\/0d3b4bc5302f8e3dd68cbb6464b888dd"},"headline":"LeetCode #300\u00a0Longest Increasing Subsequence Solution &#038; Explanation","datePublished":"2024-01-08T13:59:52+00:00","dateModified":"2024-02-20T07:31:28+00:00","mainEntityOfPage":{"@id":"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/"},"wordCount":360,"commentCount":0,"publisher":{"@id":"https:\/\/zyrastory.com\/#\/schema\/person\/0d3b4bc5302f8e3dd68cbb6464b888dd"},"image":{"@id":"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/#primaryimage"},"thumbnailUrl":"https:\/\/zyrastory.com\/wp-content\/uploads\/2024\/01\/300_Examples_Constraints.webp","keywords":["Blind 75","LeetCode C#Solution","LeetCode Java Solution","LeetCode JavaScript Solution","LeetCode Medium","LeetCode Python3 Solution"],"articleSection":["LeetCode Solution"],"inLanguage":"zh-TW","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/","url":"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/","name":"LeetCode #300\u00a0Longest Increasing Subsequence Solution & Explanation - zyrastory\u7a0b\u5f0f\u7f8e\u98df\u7814\u7a76\u4e2d\u5fc3","isPartOf":{"@id":"https:\/\/zyrastory.com\/#website"},"primaryImageOfPage":{"@id":"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/#primaryimage"},"image":{"@id":"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/#primaryimage"},"thumbnailUrl":"https:\/\/zyrastory.com\/wp-content\/uploads\/2024\/01\/300_Examples_Constraints.webp","datePublished":"2024-01-08T13:59:52+00:00","dateModified":"2024-02-20T07:31:28+00:00","description":"This is a classic dynamic programming problem, return\u00a0the length of the longest\u00a0increasing subsequence. C#, Java, Python3, JS solution","breadcrumb":{"@id":"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/#breadcrumb"},"inLanguage":"zh-TW","potentialAction":[{"@type":"ReadAction","target":["https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/"]}]},{"@type":"ImageObject","inLanguage":"zh-TW","@id":"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/#primaryimage","url":"https:\/\/zyrastory.com\/wp-content\/uploads\/2024\/01\/300_Examples_Constraints.webp","contentUrl":"https:\/\/zyrastory.com\/wp-content\/uploads\/2024\/01\/300_Examples_Constraints.webp","width":721,"height":715},{"@type":"BreadcrumbList","@id":"https:\/\/zyrastory.com\/en\/coding-en\/leetcode-en\/leetcode-300-longest-increasing-subsequence-solution-and-explanation-en\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\u9996\u9801","item":"https:\/\/zyrastory.com\/"},{"@type":"ListItem","position":2,"name":"LeetCode #300\u00a0Longest Increasing Subsequence Solution &#038; Explanation"}]},{"@type":"WebSite","@id":"https:\/\/zyrastory.com\/#website","url":"https:\/\/zyrastory.com\/","name":"zyrastory\u7a0b\u5f0f\u7f8e\u98df\u7814\u7a76\u4e2d\u5fc3","description":"\u53ea\u662f\u500b\u559c\u6b61\u5206\u4eab\u7684\u5c0f\u5de5\u7a0b\u5e2b","publisher":{"@id":"https:\/\/zyrastory.com\/#\/schema\/person\/0d3b4bc5302f8e3dd68cbb6464b888dd"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/zyrastory.com\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"zh-TW"},{"@type":["Person","Organization"],"@id":"https:\/\/zyrastory.com\/#\/schema\/person\/0d3b4bc5302f8e3dd68cbb6464b888dd","name":"zyrastory","image":{"@type":"ImageObject","inLanguage":"zh-TW","@id":"https:\/\/zyrastory.com\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/c0f3eeb72ed82297486aa0323b8a29fb?s=96&d=identicon&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/c0f3eeb72ed82297486aa0323b8a29fb?s=96&d=identicon&r=g","caption":"zyrastory"},"logo":{"@id":"https:\/\/zyrastory.com\/#\/schema\/person\/image\/"},"sameAs":["https:\/\/zyrastory.com"],"url":"https:\/\/zyrastory.com\/author\/zyrastory\/"}]}},"uagb_featured_image_src":{"full":false,"thumbnail":false,"medium":false,"medium_large":false,"large":false,"1536x1536":false,"2048x2048":false},"uagb_author_info":{"display_name":"zyrastory","author_link":"https:\/\/zyrastory.com\/author\/zyrastory\/"},"uagb_comment_info":0,"uagb_excerpt":"This is a classic dynamic programming problem, return\u00a0t...","_links":{"self":[{"href":"https:\/\/zyrastory.com\/wp-json\/wp\/v2\/posts\/6536"}],"collection":[{"href":"https:\/\/zyrastory.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zyrastory.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zyrastory.com\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zyrastory.com\/wp-json\/wp\/v2\/comments?post=6536"}],"version-history":[{"count":0,"href":"https:\/\/zyrastory.com\/wp-json\/wp\/v2\/posts\/6536\/revisions"}],"wp:attachment":[{"href":"https:\/\/zyrastory.com\/wp-json\/wp\/v2\/media?parent=6536"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zyrastory.com\/wp-json\/wp\/v2\/categories?post=6536"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zyrastory.com\/wp-json\/wp\/v2\/tags?post=6536"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}