LeetCode 300：最长上升子序列

题目描述

标准解法一：DP $O(n^2)$

$d[i] = max(d[j])+1, 0 ≤ j < i \&\& nums[j] > nums[i]$

即$d[i]$表示以$nums[i]$结尾的最长递增子序列长度

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n=(int)nums.size();
        if (n == 0) return 0;
        vector<int> dp(n, 0);
        for (int i = 0; i < n; ++i) {
            dp[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        return *max_element(dp.begin(), dp.end());
    }
};

标准解法二：贪心+二分 $O(nlogn)$

　　思路：记录长度为i的LIS的最小尾元素d[i]

贪心贪什么？

　　贪尾元素的最小，从而保证每个长度为i的递增子序列（IS，Increasing Sequence）都是最容易扩充的。

二分分什么？

　　分最小尾元数组d，当num[i]大于当前最大长度len对应的尾元d[len]时，秩序将num[i]“插入”LIS（直接令d[++len]=num[i]即可完成更新d与len）；而如果无法插入当前的LIS，则需要考虑更新之前的IS，因为每个IS都有可能成为LIS。所以需要找到d[k] < num[i] < d[k+1]，也就是找到第一个比num[i]小的尾元d[k]，这里就用到了二分。然后把num[i]“插到”d[k]之后（更新d[k+1]=num[i]）。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len = 1, n = (int)nums.size();
        if (n == 0) return 0;
        vector<int> d(n + 1, 0);
        d[len] = nums[0];
        for (int i = 1; i < n; ++i) {
            if (nums[i] > d[len]) d[++len] = nums[i];
            else{
                int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (d[mid] < nums[i]) {
                        pos = mid;
                        l = mid + 1;
                    }
                    else r = mid - 1;
                }
                d[pos + 1] = nums[i];
            }
        }
        return len;
    }
};

个人解法 DP

　　思路类似标准解法一，用map P记录以nums[i]结尾的的最大递增子序列（LIS），每次取最大的LIS长度P[nums[j]]使得nums[i]>nums[j]保留

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        map<int, int> P;    // 使用map记录num[i]结尾的LIS

        for (int i = 0; i < nums.size(); i++) {
            P[nums[i]] = 1; // 初始化为1（也就是只有自己）
        }

        for (int i = 0; i < nums.size(); i++) {
            int j;
            for (j = 0; j < i; j++) {
                if (nums[i] > nums[j] && P[nums[i]] < P[nums[j]]+1) {
                    P[nums[i]] = P[nums[j]]+1;  // 取最大的一个
                    // cout << nums[i] << " " << P[nums[i]] << endl;
                }
            }
        }

        int max = 0;
        for (auto it = P.begin(); it != P.end(); it++) {
            if ((*it).second > max) {
                max = (*it).second;
            }
        }
        return max;
    }
};

　　总结一下，DP解这题的思路只需由i建立nums[i]与dp数组dp[i]的联系，而无需用到map进行具体数值的映射。此外，对max的处理不够简略，比较混乱

参考

官方题解