C++ solution that can deal with any increasing (K+1)-tuple subsequence


  • 0
    D

    Use an array minL[K], where minL[x] save the smallest increasing x-tuple subsequence (smallest means the value of the last entry is smallest). Then for each nums[i], update minL: i.e. find the first j that minL[j] >= nums[i] and then update minL[j] as nums[i] if j<K, otherwise we find an increasing (K+1)-tuple subsequence, output true;

    class Solution {
    public:
        bool increasingTriplet(vector<int>& nums) {
            const int K=2;
            int len=nums.size(), i, j, minL[K];
            fill_n(minL, K, INT_MAX);
    
            for(i=0; i<len;++i)
            {
                for(j=0;j<K && nums[i]>minL[j];++j);
                if(j==K) return true;
                else minL[j] = nums[i];
            }
            return false;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.