题意理解

在一个数组arr中，我们可以从前往后按照顺序选择一些数字，构成一个子序列a。要求子序列从前往后是严格递增的，即对于任意 $i < j$ ，必须满足 $a [i] < a [j]$ 。现在我们要找出所有这样的子序列中，最长长度为多少。

方法一

贪心+二分
我们注意到，当某两个严格上升子序列长度一样时，如果选择结尾数字较小的子序列，那么后面更有可能扩张子序列长度。例如[6,1,5,3,4]，当遍历到3时，长度为2的子序列有[1,5]和[1,3]。此时后者时更优的，因为可以组成[1,3,4]；当然如果最后时大于4的数则两者一样优。总的来说，长度相同时结尾取小的数更优。

使用数组t来记不同长度的严格上升子序列的结尾的数值。从前往后遍历arr：
1）若arr[i]大于t的最后一个数，则整体的最长严格上升子序列长度可以加1，并在t末尾插入arr[i]。
2）否则，记以arr[i]结尾的子序列长度len+1，比较arr[i]和t[len]，选较小值存在t[len]的位置。

可以保证，t数组一直时有序的。操作1显然。操作2更新后，新的t[len]小于旧的t[len]小于t[len+1]。如果新t[len]小于t[len-1]，则此时长度为len+1的子序列不严格上升，存在矛盾。

因此，我们不用求出以arr[i]结尾的子序列长度，只要通过二分发查找arr[i]在t中对应的位置即可。

最终的输出为t数组的长度。

整个过程中t数组的示意图如下： alt

具体代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型vector 给定的数组
     * @return int整型
     */
    int found(vector<int> t, int target, int l, int r)
    {
        while (l<=r)
        {
            int mid = l + (r-l)/2;
            if (t[mid] == target) return mid;
            if (t[mid] > target) r = mid - 1;
            else l = mid + 1;
        }
        return l;
    }
    
    int LIS(vector<int>& arr) {
        // write code here
        //t[i]记录长度为i的严格上升子序列的结尾数字
        vector<int> t;
        if (!arr.size()) return 0;
        t.push_back(arr[0]);
        for (int i=1;i<arr.size();i++)
        {
            if (arr[i]>t[t.size()-1])
            {
                t.push_back(arr[i]);
            }
            else if (arr[i]<t[t.size()-1])
            {
                //found函数用来找到arr[i]在t数组中的位置
                int index = found(t,arr[i],0,t.size());
                t[index] = arr[i];
            }
        }
        return t.size();
    }
};

时间复杂度： $O (N l o g N)$ 。遍历了一遍数组arr，每次做一遍二分查找。
空间复杂度： $O (N)$ 。开辟了新的一维数组t，长度最多和arr一样。

题解 | #最长上升子序列(二)#

题意理解

方法一