C++ solution similar to the question: Longest Increasing Subsequence


  • 0
    X
    class Solution {
    public:
        bool increasingTriplet(vector<int>& nums) {
            if (nums.size() <= 2) return false;
            int n = nums.size();
            int longestSequence = 1;
            int len_min[4] = { 0 };
            len_min[1] = nums[0];
            
            for (int i = 1; i < n; i++) {
                if (len_min[longestSequence] < nums[i]) {
                    longestSequence++;
                    if (longestSequence >= 3) return true;
                    len_min[longestSequence] = nums[i];
                } else {
                    //find in len_min until num[i] > len_min[len]
                    int len = longestSequence;
                    while (len >= 1 && nums[i] <= len_min[len]) len--;
                    len_min[len + 1] = nums[i];
                }
            }
            
            return false;
        }
    };

Log in to reply
 

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