Test cases incomplete for Longest Increasing Subsequence (LIS)


  • 0
    N

    My first solution was accepted but it failed on this particular case: [2, 15, 3, 7, 8, 6, 18]. The expected length is 5 for [2, 3, 7, 8, 18] but my solution returned 4.

    int lengthOfLIS(vector<int>& nums) {
            if (nums.size() == 0) {
                return 0;
            }
            int n = nums.size();
            int maxLen = 0;
            for (int i = 0; i < n; i++) {
                int len = 1;
                int curr = nums[i];
                for (int j = i; j < n; j++) {
                    if (nums[j] > curr) {
                        len++;
                        curr = nums[j];
                    }
                }
                
                if (len > maxLen) {
                    maxLen = len;
                }
            }
            
            for (int i = n - 1; i > -1; i--) {
                int len = 1;
                int curr = nums[i];
                for (int j = i; j > -1; j--) {
                    if (nums[j] < curr) {
                        len++;
                        curr = nums[j];
                    }
                }
                
                if (len > maxLen) {
                    maxLen = len;
                }
            }
            
            return maxLen;

  • 0

    Thanks for improving LeetCode! 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.