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

算法 1

(动态规划) $O(n)O(n)$

状态表示：$f[i]f[i]$，表示以 arr[i] 结尾的最大上升子序列的长度。 状态计算：$f[i]=max(f[i],f[j]+1),j\in [0,i-1]f[i]\; =\; max(f[i],\; f[j]\; +\; 1),\; j\; \backslash in\; [0,\; i\; -\; 1]$ 边界：

1. 初始化：f[i] = 1, 表示以当前数结尾的最长上升子序列的长度为 1

2. 答案：

   所有 f[i] 的最大值就是最长上升子序列的长度 cnt

   需要输出最长上升子序列，则从后往前寻找，如果当前位置的 f[i] == cnt (长度)，则将其加入到答案中（从后往前放到答案中），并将 cnt --

时间复杂度

$O(n^2)O(n^2)$

空间复杂度

$O(n)O(n)$

class Solution {
public:
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */
    vector<int> LIS(vector<int>& arr) {
        int n = arr.size();
        vector<int> f(n);
        int cnt = 0;
        for (int i = 0; i < n; i ++ ) {
            f[i] = 1;
            for (int j = 0; j < i; j ++ ) {
                if (arr[i] > arr[j]) 
                    f[i] = max(f[i], f[j] + 1);
            }
            cnt = max(cnt, f[i]);
        }
        
        // 从后往前找，找到的就是字典序最小的序列
        vector<int> res(cnt);
        for (int i = n - 1, j = cnt; j > 0; i -- ) {
            if (f[i] == j)
                res[ -- j] = arr[i];
        }
        return res;
    }
};

算法 2

(贪心 + 二分) $O(n)O(n)$

参考题解：https://www.acwing.com/solution/content/2192/ f[i] 用来存储长度为 i + 1 的最长上升子序列结尾的最小值，可证明 $ff$ 是单调递增的，即对于长度为 x 的最长上升子序列的结尾最小值 w 和 长度为 y 的最长上升子序列的结尾最小值 v，如果 x < y 则必然存在 w < v。证明见 g[i] 用于存储以当前数 a[i] 结尾的最长上升子序列的长度。 cnt：表示最长上升子序列的长度，初始值为 0

算法步骤：

1. 初始化 f[cnt ++ ](f[0]) = a[0], g[0] = 1

2. 下标从 1 开始遍历数组 a

   • 如果当前数大于目前上升子序列结尾的最小值即 a[i] > f[cnt - 1] 时，直接把 a[i] 加入到 f 数组中，长度 + 1（cnt + 1），并作为当前最长上升子序列新的结尾，同时更新 g[i] = cnt。
   • 否则 a[i] <= f[cnt - 1]，此时需要从 f 数组中找到第一个大于等于 a[i] 的数，假设它的下标为 k，那么以下标 k 结尾的最长上升子序列的长度为 k + 1，更新长度为 k + 1 的最长上升子序列的结尾最小值为 a[i]。 由于 f 数组是单调的，所以可以使用二分在 $O(long)O(long)$ 的时间内找到 k 然后更新最小值，即f[k] = a[i]，同时更新 g[i] = k + 1;

3. 最后要输出序列，只需从后往前扫描 g 数组，如果 g[i] == cnt 则将其加入到答案中，且 cnt -- 。

时间复杂度

$O(nlogn)O(nlogn)$

空间复杂度

$O(n)O(n)$

class Solution {
public:
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */
    vector<int> LIS(vector<int>& a) {
        int n = a.size();
        int cnt = 0;
        
        vector<int> f(n), g(n);
        f[cnt ++ ] = a[0], g[0] = 1;
        for (int i = 1; i < n; i ++ ) {
            if (a[i] > f[cnt - 1]) f[cnt ++ ] = a[i], g[i] = cnt;
            else {
                int l = 0, r = cnt - 1;
                while (l < r) {
                    int mid = l + r >> 1;
                    if (f[mid] >= a[i]) r = mid;
                    else l = mid + 1;
                }
                f[l] = a[i];
                g[i] = l + 1;
            }
        }
//         cout << cnt << endl;

//         for (int i = n - 1; i >= 0; i -- ) cout << g[i] << " ";
        
        vector<int> res(cnt);
        for (int i = n - 1; i >= 0; i -- ) {
            if (g[i] == cnt)
                res[ -- cnt] = a[i];
        }
        return res;
    }
};