Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms / 8 / e / Solution

For local sequence alignment without mismatches, let $L_{i,j}$ maximize the score of alignments of a suffix of each prefix of lengths $i,j$, allowing both suffixes to be empty. Initialize $L_{i,0}=L_{0,j}=0$ and fillZero starts a new alignment; the remaining candidates append the possible last columns. The same optimal-substructure argument as before proves the recurrence. Because $g\ge 0$, an alignment with a negative-scoring leading portion can be improved by dropping that portion, which is exactly what the zero reset permits.

Return ${\max }_{0\le i\le m,0\le j\le n}{L}_{i,j}$, since an optimal pair of substrings may finish before either full string ends. The time is $O(mn)$ for positive input lengths, with $O(mn)$ full-table space or linear rolling-row space for the score alone. If an alignment is wanted, start alignment traceback at a maximum entry and stop at zero. No mismatching diagonal is introduced.