In many algorithms, such as the solution to the longest-subsequence problem using dynamic programming, finding the length of an answer (or signaling the nonexistence of an answer) is easy, but recovering the answer itself (in this case, a substring of the maximum possible length) requires some modifications to the algorithm.
Is there any algorithm where doing so necessitates an increase in the time-complexity of the algorithm?
Note that a change in the big-O complexity of the algorithm as written is enough (for example a change from $O(n)$ to $O(n \ln n)$.
Nontrivial, here, means that the answer should refer to an algorithm which can be modified to return the answer (for example, by storing a table), not a problem for which there is a, say, $O(1)$ algorithm that says if an answer exists and a completely different $O(2^n)$ algorithm that can find the answer.