Longest Monotone Sequence and Palindromes

Problem: Given an array of integers, find the longest subsequence of elements which monotonically increases. for ex. array = {1 4 8 2 5 7 3 4 6}, the longest subsequence = {1 2 3 4 6}

Solution: show

Let us construct the solution using the LCS problem. LCS is longest common subsequence, which says that given two string X, Y find the longest common subsequence between them, for ex. if X = {a b c a b c} and Y = {b a c b a c} then a possible LCS(X, Y) = {b c b c}. LCS problem can be solved using dynamic programming in O(n^2).

We can solve the longest monotonically increasing sequence problem using the solution to LCS. Let X = original string. Let Y = sort X (increasing order). LCS(X, Y) gives the desired answer (easy to observe).

There is a faster O(n log n) algorithm (for details check here)

Problem: Given a string, find the longest size palindrome in the string. for ex. string = "aaabbccaccbaaa", solution = "bccaccb"

Solution: show

The trivial solution is to check if a palindrom of all possible size starts from a given index. For a index i in array, the possible possitions to test are i < j <= n. Total time taken = O(n^3). We can solve this problem using Longest Common Substring and suffix trees to solve this problem in O(n) time.