Question 8 - Maximum Subsequence
- Problem Sheet
- Beware! This problem does not have a 'clever' solution, it is just outright hard. You will basically perform a depth-first search of all the possible subsequences of each of the words, occupying an enormous amount of time and space - hence the restriction on the input that the product space will be small enough to fit as an integer dereferencing a single linear array. This is necessary because doing arbitrarily dimensioned arrays can become quite expensive in most languages, in terms of the additional data structure overhead and dereferencing time needed. It is a simple optimisation to first eliminate those letters which will *NEVER* participate in a common subsequences, saving us an exponential amount of time per letter removed compared to the linear time needed to remove them.
- Sample Solution [input=>output]