Example given in problem description is wrong?

  • 0

    The problem descriptions says:

    Given [10, 9, 2, 5, 3, 7, 101, 18].
    The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4.

    However, this is incorrect. The provided subsequence is missing the 5 that has mysteriously disappeared.
    In fact, the longest increasing subsequence here is is [3, 7, 101] of length 3.

    Am I missing something or is the question phrased inappropriately?

    Thank you!

  • 0

    Hi Gragus,

    You are interpreting the problem as the problem of finding the longest increasing contiguous subsequence. However, for the longest increasing subsequence problem the elements in the subsequence can be spaced out or can have gaps in between. As long as the elements in the subsequence are in increasing order, we are fine. Hope that helps.


  • 0

    Thank you, Ashish.
    What you say makes sense given the example. I wish the question would have been phrased in a clearer way since "sequence" usually carries the co-notation of being continuous. However, your clarification helps.

    Thank you,


Log in to reply

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