给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:

• 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
• 你算法的时间复杂度应该为 O(n2) 。

进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

Solution

• 动态规划算法
• dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。

# @lc code=start
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = [1]*len(nums)
        for i in range(len(nums)):
            for j in range(0, i):
                if nums[i]>nums[j]:
                    dp[i]=max(dp[i],dp[j]+1)
        res = 0
        for i in range(len(dp)):
            res=max(res,dp[i])
        return res
# @lc code=end

cpp

// @lc code=start
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if(n<2) return n;

        vector<int> dp(n, 1);
        for(int i=1; i<n; ++i){
            for(int j=0; j<i; ++j)
                if(nums[i]>nums[j])
                    dp[i] = max(dp[i], dp[j]+1);
        }
        
        int res = 0;
        for(int i=0; i<n; ++i)
            res = max(res, dp[i]);
        return res;
    }
};
// @lc code=end

贪心算法

参考 LeetCode官方

思路：如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if(n<2) return n;

        vector<int> d(n+1, 0);
        int len = 1;
        d[len] = nums[0];
        for(int i=1; i<n; ++i){
            if(nums[i] > d[len])
                d[++len] = nums[i];
            else{
                // 二分查找寻找第一个比 nums[i] 小的更新位置
                int l=1, r=len, pos=0;
                while(l<=r){
                    int mid = (l+r)>>1;
                    if(d[mid]<nums[i]){
                        l = mid+1;
                        pos = mid;
                    } else {
                        r = mid-1;
                    }
                }
                d[pos+1] = nums[i];
            }
        }
        return len;
    }
};

给定数组arr, 返回arr的最长递增子序列。

• 动态规划，时间复杂度O(N^2)的方法

1. 生成长度为N的数组dp, dp[i]表示在以arr[i]这个数结尾的情况下，arr[0…i]中的最大递增序列长度。

2. 对第一个数arr[0]来说，令dp[0] = 1,接下来，从左到右依次计算出每个数结尾的情况下的最长递增序列长度。

3. 计算dp[i]，如果最长递增子序列以arr[i]结尾，那么arr[0,…,i-1]中所有比arr[i]小的数都可以作为倒数第二个数

   所以 dp[i] = max{ dp[j] + 1} (0 <=j < i, arr[j] < arr[i])， 如果arr[0,…,i-1]中所有数都不比arr[i]小，令dp[i] = 1。

4. 根据求出的dp数组，得到最长递增子序列。遍历dp数组，找到最大值以及位置，并开始逆序还原出决策路径。

vector<int> generateLIS(vector<int> &arr, vector<int> &dp){
    int len = 0; int index = 0;
    for (int i = 0; i < dp.size(); i++) { //寻最长递增子序列末尾的位置和值
        if (dp[i] > len) {
            len = dp[i];              // 最长序列长度
            index = i;                // 最长序列末位置
        }
    }
    vector<int> lis(len, 0);
    lis[--len] = arr[index];
    for (int i = index; i >= 0; i--){
        if (arr[i] < arr[index] && dp[i] == dp[index] - 1){  //从后往前找子序列
            lis[--len] = arr[i];
            index = i;
        }
    }
    return lis;
}
/* input
2 1 5 3 6 4 8 9 7
*/
/* output
1 3 4 8 9
*/

• 二分法，时间复杂度O(NlogN)的方法

以arr=[2,1,5,3,6,4,8,9,7]为例进行说明：

1. 初始时，dp[0]=1, ends[0]=2, rights = 0, 有效区 ends[0…0],ends[0] = 2, 长度为1，结尾为2

2. arr[1] = 1, 在有效区ends[0,…0]找最左边大于或等于arr[1]的数，发现ends[0] =2 >arr[1], 表示以arr[1]结尾的最长序列只有一 个，dp[1] = 1, ends[0] = 1 (用1替换了原来的2)

3. arr[2] = 5, 在有效区ends[0,..0]找最左边大于或等于arr[2]的数，发现并没有，则ends的有效长度+1， end[1] = 5, 有效区扩大，dp[2] = 2. arr[0,1] = {1, 5}

参考：动态规划C++实现–最长递增子序列