LIS

300. Longest Increasing Subsequence

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

For example, Given [10, 9, 2, 5, 3, 7, 101, 18], The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in $$ O(n^2) $$ complexity.

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

(1)动态规划的算法

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.empty()) return 0;
        vector<int> res(nums.size(), 1);

        int maxLen = 1;
        for(int j = 1; j < nums.size(); ++j){
            for(int i = 0; i < j; ++i){
                if(res[j] < res[i] + 1 && nums[j] > nums[i])
                    res[j] = res[i] + 1;
            }
            maxLen = max(res[j], maxLen);
        }
        return maxLen;
    }
};

(2)运用二分，时间复杂度$$O(nlogn)$$

class Solution {
public:
    int lengthOfLIS(vector<int>& nums){
        if(nums.empty())    return 0;

        vector<int> res;

        for(auto num:nums){
            auto it = lower_bound(res.begin(), res.end(), num);

            if(it == res.end())  
                res.push_back(num);
            else                    
                *it = num;
        }
        return res.size();
    }
};

334. Increasing Triplet Subsequence

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should: Return true if there exists i, j, k such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false. Your algorithm should run in O(n) time complexity and O(1) space complexity.

Examples: Given [1, 2, 3, 4, 5], return true.

Given [5, 4, 3, 2, 1], return false.

(1)解法一：求出LIS，判断长度是否大于3

(2)解法二：

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int min = INT_MAX;
        int mid = INT_MAX;

        for(auto num:nums){
            if(num < min)
                min = num;
            else if(num > min){
                if(num > mid)
                    return true;
                else
                    mid = num;
            }
        }
        return false;
    }
};