Search code examples
algorithmdynamic-programmingsubsequence

Does a subsequence need to be continuous

I am new to Dynamic Programming and was reading on the Longest Increasing Subsequence(LIS) problem.

The solution stated that the sequence need not be continuous as in the original array. Elements can be skipped in between; but I was under another impression.

Could you please help clarify this confusion.

Say for example: a = {10,22,9,33,55,66,12,90} the LIS is {10,22,33,55,66,90} => 6

However, I thought it would be {33,55,66}

Thanks

Solution

  • Subsequence doesn't need to be continous. A Subsequence is formed by deleting zero or more elements from an array. A subaaray on the other hand is always continous. Lets's take your example:

    a = {10,22,9,33,55,66,12,90}

    Here,{10,22,33,55,66,90} is the longest increasing subsequence and {33,55,66} is the longest increasing subarray.

    So, what you are basically answering is a solution to the longest increasing subarray problem.