We extend the algorithm of Galil and Giancarlo, which speeds up dynamic programming in the case of concave cost functions, such that a compact representation of all optimal solutions is computed. Compared to the Galil-Giancarlo algorithms our time bound grows only by a small constant factor. With a compact representation, we develop efficient algorithms for the solution of problems in molecular biology concerning the computation of all optimal local alignments and all optimal subalignments in genetic sequences.