{"id":1291,"date":"2024-05-07T11:53:09","date_gmt":"2024-05-07T11:53:09","guid":{"rendered":"https:\/\/www.gislxz.com\/?p=1291"},"modified":"2024-05-07T11:53:09","modified_gmt":"2024-05-07T11:53:09","slug":"leetcode-300-%e6%9c%80%e9%95%bf%e9%80%92%e5%a2%9e%e5%ad%90%e5%ba%8f%e5%88%97","status":"publish","type":"post","link":"https:\/\/www.gislxz.com\/index.php\/2024\/05\/07\/leetcode-300-%e6%9c%80%e9%95%bf%e9%80%92%e5%a2%9e%e5%ad%90%e5%ba%8f%e5%88%97\/","title":{"rendered":"Leetcode 300. \u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217"},"content":{"rendered":"\n<p><a href=\"https:\/\/leetcode.cn\/problems\/longest-increasing-subsequence\/description\/\" target=\"_blank\"  rel=\"nofollow\" >300. \u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217 - \u529b\u6263\uff08LeetCode\uff09<\/a><\/p>\n\n\n\n<p>\u4e00\u5f00\u59cb\u60f3\u7528dfs\uff0b\u526a\u679d\uff0c\u8d85\u65f6<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\r\npublic:\r\n    unordered_map&lt;int,int> max_length;\r\npublic:\r\n    int search(vector&lt;int>&amp; nums,int length,int index,int last){\r\n        if(index == nums.size())\r\n            return length;\r\n        if(max_length.count(last) == 0)\r\n            max_length.insert({last,length});\r\n        else if(length&lt;max_length&#91;last])\r\n            return INT_MIN;\r\n        else\r\n            max_length&#91;last] = length; \r\n        if(last>=nums&#91;index])\r\n            return search(nums,length,index+1,last);\r\n        return max(search(nums,length+1,index+1,nums&#91;index]),search(nums,length,index+1,last));\r\n    }\r\n    int lengthOfLIS(vector&lt;int>&amp; nums) {\r\n        return search(nums,0,0,INT_MIN);\r\n    }\r\n};<\/code><\/pre>\n\n\n\n<p>\u76f4\u63a5DP<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\r\npublic:\r\n    int lengthOfLIS(vector&lt;int>&amp; nums) {\r\n        int result = 0;\r\n        vector&lt;int> maxLength(nums.size());\r\n        for(int i = 0;i&lt;nums.size();i++){\r\n            for(int j = i - 1;j>=0;j--){\r\n                if(nums&#91;i]>nums&#91;j])\r\n                    maxLength&#91;i] = max(maxLength&#91;j]+1,maxLength&#91;i]);\r\n            }\r\n        }\r\n        for(auto i : maxLength){\r\n            result = max(result,i);\r\n        }\r\n        return result+1;\r\n    }\r\n};<\/code><\/pre>\n\n\n\n<p>\u4f46\u90fd\u4e0d\u662f\u6700\u4f18\u89e3<\/p>\n\n\n\n<p>\u9898\u89e3\uff1a<a href=\"https:\/\/leetcode.cn\/problems\/longest-increasing-subsequence\/solutions\/2147040\/jiao-ni-yi-bu-bu-si-kao-dpfu-o1-kong-jia-4zma\" target=\"_blank\"  rel=\"nofollow\" >300. \u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217 - \u529b\u6263\uff08LeetCode\uff09<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>300. \u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217 &#8211; \u529b\u6263\uff08LeetCode\uff09 \u4e00\u5f00\u59cb\u60f3\u7528dfs\uff0b\u526a\u679d\uff0c\u8d85\u65f6 \u76f4\u63a5DP \u4f46\u90fd\u4e0d\u662f\u6700\u4f18\u89e3 \u9898\u89e3\uff1a300. \u6700 &#823","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[1],"tags":[],"class_list":["post-1291","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/posts\/1291","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/comments?post=1291"}],"version-history":[{"count":1,"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/posts\/1291\/revisions"}],"predecessor-version":[{"id":1292,"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/posts\/1291\/revisions\/1292"}],"wp:attachment":[{"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/media?parent=1291"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/categories?post=1291"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/tags?post=1291"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}