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
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