3/14题解

给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:
不需要严格连续。
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2)
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
方法一：动态规划
状态转移方程：dp[i]=max(dp[j])+1,满足0<=j<i且nums[i]>num[j]

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.size()==0) return 0;
        vector<int>dp(nums.size(),0);//先统一置0
        for(int i=0;i<nums.size();i++)
        {
            dp[i]=1;
            for(int j=0;j<i;j++)
            {
                if(nums[i]>nums[j])
                {
                    dp[i]=max(dp[j]+1,dp[i]);
                }
            }
        }
        return *max_element(dp.begin(),dp.end());//返回vector最大元素的函数
    }
};

方法二：贪心+二分查找
考虑一个简单的贪心，如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len=1;
        int n=(int)nums.size();
        if(n==0) return 0;
        vector<int> res(n+1,0);
        res[len]=nums[0];
        for(int i=1;i<n;i++)
        {
            if(nums[i]>res[len])
            {
                res[++len]=nums[i];//如果num大于res数组的所有数，往后添加
            }
            else
            {
                int l=0,r=len,pos=0;//若小于，则二分查找num[i]的插入点，如果num[i]小于这里面的所有数，则令res[1]=num[i]，因此令pos=0
                while(l<=r)
                {
                    int mid=(l+r)/2;
                    if(res[mid]<nums[i])
                    {
                        pos=mid;
                        l=mid+1;
                    }
                    else
                    {
                        r=mid-1;
                    }
                }
                res[pos+1]=nums[i];
            }
        }
        return len;
    }
};