题意理解

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

方法一

动态规划
用一个数组dp记录以原数组中每个数字结尾的最长严格上升子序列的长度。在初始状态下，dp的值均为1，因为每个数字本身构成严格上升子序列。

我们从前往后更新dp。对于每个数arr[i]，依次遍历它前面的数字arr[j] ( $i < j$ )。如果前面的数字小，说明以arr[j]结尾的最长严格子序列加上arr[i]之后仍然是严格上升的（新的子序列记为a），此时以arr[i]结尾的最长严格上升子序列的长度可能得到更新，当然也可能不变（a的长度小于等于dp[i]）。

状态转移方程为：
$d p [i] = m a x (d p [i], d p [j] + 1)$

以[6,1,3,2,7]为例，dp数组每一轮循环的更新过程如图所示：

alt

具体代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型vector 给定的数组
     * @return int整型
     */
    int LIS(vector<int>& arr) {
        // write code here
        //dp[i]记录以第i个数字结尾的最长严格上升子序列
        vector<int> dp;
        //初始化为1
        for (int i=0;i<arr.size();i++)
            dp.push_back(1);
        for (int i=1;i<arr.size();i++)
        {
            for (int j=0;j<i;j++)
                //如果前面的数小于当前arr[i]，则以当前数字结尾的最长上升子序列可能更新
                if (arr[j]<arr[i])
                    dp[i] = max(dp[j]+1,dp[i]);
        }
        int max_len=0;
        for (int i=0;i<dp.size();i++)
            if (dp[i]>max_len) max_len = dp[i];
        return max_len;
    }
};

时间复杂度： $O (N^{2})$ 。使用了双重循环来更新dp数组。
空间复杂度： $O (N)$ 。开辟了新的一维数组dp，长度和arr一样。

方法二

贪心+二分
我们注意到，当某两个严格上升子序列长度一样时，如果选择结尾数字较小的子序列，那么后面更有可能扩张子序列长度。例如[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数组的长度。

具体代码如下：

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一样。

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

题意理解

方法一

方法二