Sangar's blog

Non overlapping Longest Increasing Subsequence (L1) And Decreasing Subsequence (L2)in array with max length (L1+L2)
By Sangar, history, 8 years ago, In English

Hello,

I have been trying this question on Spoj BatMan2

It requires to find a LIS from left to right and a LIS from right to left but non overlapping

Someone suggested this solution in comments

really aww sum problem cant wait to share the idea simply go one way and give each number to a increasing or decreasing or nothing max among three is ans

can anyone help with this DP problem

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
8 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

You can solve this problem in O(n3)

dp(r, b, c) =  Maximum number of rooms they can visit from the room r, if the last room visited by Batman was the room b and the last room visited by Catwoman was the room c

Transitions are simple, Batman can visit a room with value v if the last room visited by him had a value strictly less than v.

Similar principle applies for catwoman

→ Reply