longest sub-sequence in both directions Given a character array A of size n, compute the length of a longest sub-sequence S of A such that, S read backward is also a sub-sequence of A.

Example: A = cabca

the sub-sequence S = abc is the longest of such sub-sequences.

reading S forward (abc): cabca

reading S reverse (cba): cabca

How to compute the length of such an S ?
One option is to reduce your problem to Longest Common Subsequence. I'll let you figure out how.