Elon Musk is building a prototype Hyperloop line that travels through cities X = x1, x2,..., xn in that order. The Hyperloop may travel through the same city multiple times. He wishes to construct a public transit service using the Hyperloop, by constructing stops at a subset of the cities on the route. In order to be useful, the transit service must stop in a list of cities in order, and then go back through those same cities in the reverse order.

To maximize the usage of the transit service, it should have as many stops as possible. For instance, consider the route X = { London (L), Kitchener (K), Hamilton (H), Burlington (B), Toronto (T), Ottawa (O), Montreal (M), Pickering (P), Toronto (T), Burlington (B), Kitchener (K) }. Two valid transit paths would be KTTK and KBTMTBK, the latter of which is optimal. Note that Montreal is only stopped at once, but the route is valid as long as it reads the same backwards and forwards.

Given a Hyperloop route X, devise a dynamic programming algorithm to find the length of the optimal (longest) transit path of X. Write the pseudocode, recurrence relation, and analyze the run time complexity of your algorithm.