Recursion Lab

Longest Palindrome Subsequence $($LPS$)$ is a "poster child" for recursion and very hard to solve in any other way. In this lab you will create class named LPS and within that class you will write two methods: lpsLength $($String str$)$ andlpsString $(...)$

Given a string str$,$

lpsLength $($String str$)$ returns the length of the LPS in str lpsString $(...)$ returns one LPS string

You may assume that the initial given string str is not an empty string.

Here are some examples.

$\backslash$table$[[$str$,$Lps length,Lps string$],[$zryxadavr$,5,$radar$],[$aaxyz$,2,$aa$],[$abcxcybza$,7,$abcxcba$],[$ATGCATCATTGACCA$,10,$ACCATTACCA$]]$

Notice that the sequence "zryxadavr" contains the palindrome subsequence "radar" within it: zryxadavr

$r$ ada $r$

In fact, "radar", which has length $5,$ is the longest palindrome that can be found embedded in "zryxadavr". We say that "radar" is the longest palindrymic subsequence $($LPS$)$ in the given string "zryxadavr".

$\backslash$table$[[$Example$1,$Example $2],[$Input string: zryxadavr,Input string: ATGCATCATTGACCA$],[$Output:$,$Output:$],[$Ips length $=5,$Ips length $=10],[$Ips string $=$ radar,Ips string $=$ ACCATTACCA$]]$

Submit you work in ONE Zip file and submit it in Canvas.

Zip filename should be in format of FirstLast$\_$Lab$2.$zip $($ex$.$ JohnDoe$\_$Lab$2.$zip$)$

Zip file should contain $4$ files only:

$(1)$ LPS$.$java