[leetcode] 300. Longest Increasing Subsequence

[leetcode] 300. Longest Increasing Subsequence

Description

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Note:

There may be more than one LIS combination, it is only necessary for you to return the length.Your algorithm should run in O(n2) complexity.Follow up: Could you improve it to O(n log n) time complexity?

分析

题目的意思是：找出一个数组中的最长递增子序列。

这题用了动态规划的方法对于每一个元素，都有可能跟前面的序列构成一个较长的上升序列，或者跟后面的序列构成一个较长的上升序列

对于题目中的例子： 1）对于10这个元素，它是第一个，所以它构成的最长上升子序列长度为1； 2）对于9这个元素，前面没有比它小的，所以它构成的最长上升子序列长度为1； 3）对于2这个元素，遍历前面的10和9，没有比它小的，所以它构成的最长上升子序列长度为1； 4）对于5这个元素，遍历前面的10，9，2，发现2比它小，所以能和2构成最长上升子序列，2的最长上升子序列的长度为1，所以5的最长上升子序列长度是1+1=2； 5）对于3这个元素，遍历前面的10，9，2，5，发现2比它小，所以能和2构成最长上升子序列，2的最长上升子序列的长度为1，所以3的最长上升子序列长度是1+1=2； 6）对于7这个元素，遍历前面10，9，2，5，3，发现2，5，3，比它小，找2，5，3谁的最长上升子序列长度最长，最长值加1，得到了长度2+1=3； 7）对于101这个元素，遍历前面的10，9，2，5，3，7，发现都比它小，找前面的10，9，2，5，3，7谁的最长上升子序列最长，发现7的子序列长度最大，最大值加1，得到长度4. 8）对于18这个元素，遍历前面的10，9，2，5，3，7，101，发现10，9，2，5，3，7比它小，找这几个元素谁的最长上升子序列最长，最长值3加1，得到了3+1=4 由此可得递推式：如果 nums[i]>nums[j] 则dp[i]=max(dp[j]+1,dp[i]);

最近猿辅导面试官跟我出了一道类似的题目，我特地用python又写了一下，这次是用二叉查找树来实现的，时间复杂度就变成了O(nlogn)，大概思路是这样，维护一个best数组，best数组是从大到小排列，当遍历nums数组的时候，用二分查找找出插入的位置，并进行插入。开始我还不太明白，后面感觉这个像插入排序算法。

代码

class Solution {public: int lengthOfLIS(vector& nums) { if(nums.size()==0){ return 0; } vector dp(nums.size(),1); int max_len=1; for(int i=1;inums[j]){ dp[i]=max(dp[j]+1,dp[i]); } } max_len=max(max_len,dp[i]); } return max_len; }};

代码二

class Solution: def binary_search(self,nums,target,start,end): if(start>=end): return start mid=start+(end-start)//2 if(nums[mid]>=target): if(mid==start or nums[mid-1] int: if(not nums): return 0 best=[nums[0]] for i in range(1,len(nums)): index=self.binary_search(best,nums[i],0,len(best)) if(index==len(best)): best.append(nums[i]) else: best[index]=nums[i] return len(best)

参考文献

​​leetcode 300. Longest Increasing Subsequence​​​​LeetCode 300. Longest Increasing Subsequence（最长递增子序列）​​​​O(n logn) Python solution with binary search​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。