LeetCode 300. Longest Increasing Subsequence

[Woodyiiiiiii]

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. 

Note:

• There may be more than one LIS combination, it is only necessary for you to return the length.
• Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

---

可以和#23对比。

经典的线性DP问题。设置一个长为同题目数组长度一样的dp一维数组，dp[i]代表位置i之前的最长公共递增公共子序列。dp[i] = max(dp[i], dp[i - j] + 1)，其中nums[j] <= nums[i] && j < i。

class Solution {
    public int lengthOfLIS(int[] nums) {
        int res = 0;
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int[] dp = new int[n];
        int i = 0, j = 0;
        dp[0] = 1;
        for (i = 1; i < n; ++i) {
            dp[i] = 1;
            for (j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            } 
        }
        
        for (i = 0; i < n; ++i) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

如果要把时间复杂度优化为O(n logn)，显然需要用到二分查找法，而二分查找法是针对有序数组的，所以我们需要对新数组(存放结果的)进行二分查找。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.empty()) return 0;
        vector<int> ends{nums[0]};
        for (auto a : nums) {
            if (a < ends[0]) ends[0] = a;
            else if (a > ends.back()) ends.push_back(a);
            else {
                int left = 0, right = ends.size();
                while (left < right) {
                    int mid = left + (right - left) / 2;
                    if (ends[mid] < a) left = mid + 1;
                    else right = mid;
                }
                ends[right] = a;
            }
        }
        return ends.size();
    }
};

上述做法实际上类似维护了一个单调栈(不保证顺序)，也扯上了些贪心的思想，每次按最小增长序列来算。用Java的话可以用一个数组来显示：

class Solution {
    
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        int len = 1;

        for (int i = 1; i < nums.length; i++) {
            int pos = binarySearch(dp,len - 1, nums[i]);
            if (pos == len && dp[pos - 1] < nums[i]) {
                dp[len++] = nums[i];
            } else {
                dp[pos] = nums[i];
            }
        }

        return len;
    }

    private int binarySearch(int[] dp, int len, int val) {
        int left = 0;
        int right = len;
        int mid = 0;

        while (left <= right) {
            mid = left + (right - left) / 2;
            if (dp[mid] == val) {
                return mid;
            } else {
                if (dp[mid] < val) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }

        return left > mid ? right + 1 : left;
    }
    
}

用了贪心的思想，维护一个最小数组队列。

时隔一年，重新写了一下做法：

class Solution {
    public int lengthOfLIS(int[] nums) {
        int len = 0, n = nums.length;
        int[] dp = new int[n + 1];
        dp[0] = -10001;
        for (int num : nums) {
            if (num > dp[len]) {
                dp[++len] = num;
            }
            for (int i = len; i > 0; --i) {
                if (num > dp[i - 1]) {
                    dp[i] = Math.min(dp[i], num);
                }
            }
        }
        return len;
    }
}

进一步优化可以用二分。

class Solution {
    public int lengthOfLIS(int[] nums) {
        int len = -1, ans = 0;
        int[] dp = new int[nums.length];
        for (int num : nums) {
            int lo = 0, hi = len + 1;
            while (lo < hi) {
                int mid = (lo + hi) >> 1;
                if (dp[mid] >= num) {
                    hi = mid;
                } else {
                    lo = mid + 1;
                }
            }
            dp[lo] = num;
            len = lo > len ? lo : len;
            ans = Math.max(len + 1, ans);
        }
        return ans;
    }
}

类似题目:

• 2311. Longest Binary Subsequence Less Than or Equal to K

---

参考资料:

1. LeetCode原题
2. [LeetCode] 300. Longest Increasing Subsequence grandyang/leetcode#300
3. https://leetcode.com/problems/longest-increasing-subsequence/discuss/74897/Fast-Java-Binary-Search-Solution-with-detailed-explanation