 Solution

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.