= 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 fill
$$
\boxed{L_{i,j}=\max\left\{0,\ L_{i-1,j}-g,\ L_{i,j-1}-g,\ L_{i-1,j-1}+1\ \text{only if }x[i-1]=y[j-1]\right\}.}
$$
Zero starts a new alignment; the remaining candidates append the possible last columns. The same optimal-substructure argument as before proves the recurrence. Because $g\geq0$, an alignment with a negative-scoring leading portion can be improved by dropping that portion, which is exactly what the zero reset permits.
Return \b[$\max_{0\leq i\leq m,\,0\leq j\leq n}L_{i,j}$], since an optimal pair of substrings may finish before either full string ends. The time is \b[$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.
Back to article page
