There's a bug in the judge system (the posted code are accepted)


  • 0
    C
    class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            int n = nums.size();
            
            vector<int> lis;
            
            for (auto a : nums)
            {
                if (lis.empty())
                    lis.push_back(a);
                else if (a < lis[0])
                    lis[0] = a;
                else if (a > lis.back())
                    lis.push_back(a);
                else
                {
                }
            }
            return lis.size();
        }
    };

  • 0
    C

    I assume the following snippets should be the correct answer. O(NlogN) time,

    class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            int n = nums.size();
            
            vector<int> lis;
            
            for (auto a : nums)
            {
                if (lis.empty())
                    lis.push_back(a);
                else if (a < lis[0])
                    lis[0] = a;
                else if (a > lis.back())
                    lis.push_back(a);
                else
                {
                    int left = 0;
                    int right = lis.size() - 1;
                    while (left <= right)
                    {
                        int mid = left + ((right - left) >> 1);
                        if (lis[mid] == a)
                        {
                            left = mid;
                            break;
                        }
                        else if (lis[mid] > a)
                            right = mid - 1;
                        else
                            left = mid + 1;
                    }
                    lis[left] = a;
                }
            }
            return lis.size();
        }
    };

  • 0

    Could you please provide a test case that should be added?


  • 0
    C

    [10,9,2,5,3,4]
    The answer should be 3. The output from the wrong snippets is 2. However, the judge still pass it.


  • 0

    Thanks. I have added your test case.


Log in to reply
 

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