Worst case is O(n^3). I messed up and evaluated my solution at O(n^4). Also, many solutions (including dynamic programming, but even an easier expand from center solution) are O(n^2).