I can't stand it when professors do that. Most of your class will be lucky if they can turn in
any solution, let alone an efficient one.
It isn't too much -- I was able to play with it in about 40 lines of code (plus another 15 for #includes and about the same main() as you have above).
The first link basically says that the simplest way to solve it is to:
1. make a sorted copy of A (call it B)
containing only unique elements
2. use the Longest Common Subsequence problem on A and B
Finding the Longest Common Subsequence is a little more involved, and requires you to be able to think of a list of things in a recursive way. That is, a list is "the first item in the list" attached to "the rest of the list". In the Algorithmist and Wikipedia examples, we turn that around: we have the "rest of the list" and "the last item in the list".
The reason for thinking of lists this way is how we can handle it. If I can do something to the last item in the list and the rest of the list, then I can process the entire list.
Here is an example: sum a list of numbers.
(1 2 3 4 5 6)
Split the list into "first item" and "rest of the list":
1 : (2 3 4 5 6)
Now I can think of the sum as 1 + (sum of rest of list). This repeats until there is no more list. Make sense?
The notation for this is x:xs (first item and rest of list). The articles work backwards, so the notation is xs:x (rest of list and last item).
The LCS problem is very similar. As input we have two lists: xs:x and ys:y. We find the LCS by breaking it down into three possibilities, and choosing the best solution:
1 2 3
|
if x==y
then return LCS(xs,ys):x
else return longest_of( LCS(xs:x,ys), LCS(xs,ys:y) )
| |
While this is all expressed in recursive terms, it can be done with just loops. You can optimize a bit by using the algorithms found in the Wikipedia article:
http://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Code_for_the_dynamic_programming_solution
In it, you first build a table to find just the
lengths of all the subsolutions, then you go backwards to reconstruct the actual solution by choosing the longer subsolutions.
Remember, you don't have to use recursion to do it -- the size of your lookup table will be a simple square array you can
new and
delete[], and the size of your result will be the value you find in your lookup array's last index [m][n].
I know this is a whole lot of stuff to wrap your head around; try to puzzle it out a bit and post back with specific problems..