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

(动态规划) $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] == j (长度)，则将其加入到答案中（从后往前放到答案中）

时间复杂度

$O(n)O(n)$

空间复杂度

$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;
    }
};