om
BAN USER
Comments (3)
Reputation 60
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
Algorithm:
Use Dynamic programming
LP(i,j) = 1 if i = j e.g A
= 1 if i = j-1 AND a[i] != a[j] e.g AB
= 2 if i = j-1 AND a[i] == a[j] e.g AA
= LP(i+1 , j-1) + 2 if i != j-1 AND a[i] == a[j] e.g: ABCBA i =0 and j=4
= max{ LP[i+1,j], LP[i,j-1]} if i != j-1 AND a[i] != a[j] e.g MNOPQ i=0 and j=4
Note: copied from the wiki
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
@ Chih.Chiu.19
- om July 27, 2013The above mention ur logic will also take o(n2) . Because it may possible that again for each new node u need to start traversing from root and move the existing node from right to left. E.g:
e.g : 5,10,8,20,6,7,4
for 5,10,8,20,6 : 20
/ \
10 6
/ \
5 8
For 5,10,8,20,6,7 =>
20
/ \
10 7
/ \ /
5 8 6
Please let me know if I am wrong