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 / d

Enumerate all pairs of contiguous substrings, run the global algorithm on each pair, and take the largest score, also allowing the empty alignment of score zero. There are $O(m^2)$ substrings of the first input and $O(n^2)$ of the second. Each call costs at most $O(mn)$ for positive lengths, giving the requested upper bound $O(m^3{n}^3)$. Substrings are contiguous; enumerating arbitrary subsequences would be a different search.