【Leetcode】300. Longest Increasing Subsequence（最大上升子序列）

叁歲伎倆 2021-12-16 12:04 223阅读 0赞

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?

题目大意：

给出一个未排序的序列，从其中找出最长的上升子序列（子序列可以不连续）。

解题思路：

给出两种解题思路。

第一种时间复杂度为n^2，方法比较直观，可以直接理解成为寻找到当前位置之前比其小的最长为，+1记录到当前位置中。

class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            int ans = 0;
            
            if(nums.size()==0) return ans;
            // 从当前位置向前找到第一个比其小的数，当前个数加一
            vector<int> dp(nums.size(), 0);
            dp[0] = 1;
            ans = 1;
            for(int i=1;i<nums.size();i++){
                int cor_max = 0;
                for(int j=i-1;j>=0;j--){
                    if(nums[j]<nums[i]){
                        cor_max = max(cor_max, dp[j]);
                    }
                }
                if(cor_max==0){
                    dp[i] = 1;
                }else{
                    dp[i] = cor_max + 1;
                }
                ans = max(dp[i], ans);
            }
            
            return ans;
        }
    };

第二种时间复杂度为nlog(n)，利用C++中的二分查找函数Binary Search。

在dp数组中我们只需要**查找第一个大于或等于当前元素的位置。更新保持dp数组中都是满足增长的最小数据，最终统计dp的长度即可。**

input: \[0, 8, 4, 12, 2\]

dp: \[0\]

dp: \[0, 8\]

dp: \[0, 4\]

dp: \[0 , 2, 12\]

class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            vector<int> dp;
            for(int i=0;i<nums.size();i++){
                auto idx = lower_bound(dp.begin(), dp.end(), nums[i]);
                if(idx == dp.end()){
                    dp.push_back(nums[i]);
                }else{
                    *idx = nums[i];
                }
            }
            return dp.size();
        }
    };

dp: \[0, 4, 12\]