LeetCode 300: 最长上升子序列

[guodongxiaren]

https://leetcode-cn.com/problems/longest-increasing-subsequence/

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。 你算法的时间复杂度应该为 O(n2) 。 进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

[guodongxiaren]

经典DP：LCS，20min写出bug free

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

                } else {
                if (nums[i] > nums[s[j]] && dp[i] < dp[s[j]] + 1) {
                    dp[i] = dp[s[j]]  + 1;
                    s[j] = i;
                }
                }

            }
            if (max < dp[i]) {
                max = dp[i];
            }
        }
        return max;
    }
};

[guodongxiaren]

TOOD：O(n log n)解法