how to approach this problem and where is overlapping subproblems ,please explain.
How to approach BRIDGES ? [dp]
Look for Longest increasing/decreasing subsequence such that it is valid for both arrays!
take parallel LIS, meaning
for i: 0 to n-1
for j: 0 to i-1
if(arr1[j]<arr1[i] && arr2[j]<arr2[i])
update dp[i]
do this for LDS(decreasing subsequence also)
i show one approach on internet , that first sort according to one array and take lis of another array and that is the ans , is that wrong?
yes it is wrong!
if you sort any of the array, you destroy the sequence!
just try coding this!
ok i will try that , but i am not destroying the sequence i am saying sorting will also effect second array according to first array.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.