0

How do I find the LIS,subsequence, with the constraint that I cant skip first and last element?

EDIT: What I actually meant was that I have to start from the beginning and end at the end.Also I want to extend this for a zigzag subsequence like Dynamic programming: Find longest subsequence that is zig zag

Community
  • 1
  • 1
marti
  • 173
  • 4
  • 11

1 Answers1

0

Implement the typical LIS algorithm, simply remove all elements smaller than the first element and bigger than the last one from the input. Only consider elements that are not the first or the last one for the solution and then append these two to the solution you find. Also in case the last element is no bigger than the first one say there is no increasing subsequence.

Ivaylo Strandjev
  • 69,226
  • 18
  • 123
  • 176
  • Wow that was quick and correct! Now how do I extend this for zigzag LIS(http://stackoverflow.com/questions/6914969/dynamic-programming-find-longest-subsequence-that-is-zig-zag?rq=1) with this same constraint? – marti Feb 05 '13 at 08:14
  • @marti I have solved the original problem on the SRM :) Unfortunately it will not be that easy to adapt the solution I propose for zig-zag sequence. You will have to make the DP a bit more complex by not considering sequences that do not start from the first element and only counting a solution for valid if it ends at the last one. – Ivaylo Strandjev Feb 05 '13 at 08:18
  • THanks Ivaylo ! How do I do that? – marti Feb 05 '13 at 08:24
  • @marti it is best to try to figure it out yourself :) hint: you will have to add some extra if-s. I usually implement LIS using recursion with memoization and in that case the extra ifs will have to check if the current index is 0 or last index in the array and do some extra stuff in these cases. – Ivaylo Strandjev Feb 05 '13 at 08:28