Longest Weird Sequence

I was doing this question.

http://www.codechef.com/problems/LWS

Finding longest weird subsequence.

My approach is to first find LIS and then LDS from the remaining string.

I know that this approach is wrong, but please anybody explain me why ??

I tried to find a counter example but failed.

Thank You. :slight_smile:

Using your approach we can always get a weird sequence but we cannot get the longest always.

Once you remove LIS that will effect the length of LDS in Remaining string

1 Like

@infinitum I still can’t find any example of that, but got the intuition of what you said… Thanks :slight_smile:

//