Increasing Triplet Subsequence | Leetcode #334

//Followup with K increasing subsequence
class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int n=nums.size();
        int k=3;
        vector<long long> increasing(k,LONG_MAX);

        //Find an increasing subsequence of length k
        for(int i=0;i<n;++i){
            for(int j=0;j<k;++j){
                if(increasing[j]>=nums[i]){
                    increasing[j]=nums[i];
                    break;
                }
            }
            if(increasing[k-1]!=LONG_MAX)
                return true;//Found increasing subsequence of length K
        }
        return false;
    }
};


class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int n=nums.size();
        int first=INT_MAX;
        int second=INT_MAX;

        //Find an increasing subsequence of length 3
        for(int i=0;i<n;++i){
            if(first>=nums[i])
                first = nums[i];
            else if(second>=nums[i])
                second = nums[i];
            else
                return true;//Length-3 increasing subsequence found
        }
        return false;
    }
};


//LIS Solution: TC->O(NlogN)
class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int n=nums.size();
        vector<int> lis;
        for(int i=0;i<n;++i){
            int lb = lower_bound(lis.begin(),lis.end(),nums[i])-lis.begin();
            if(lb==lis.size())
                lis.push_back(nums[i]);
            else
                lis[lb] = nums[i];
        }
        return lis.size()>=3;
    }
};