The seasoned taste maker

You are determined on making the most sonically pleasing playlist the world has ever heard. As a connoisseur of music, you realize that the order in which the songs are presented is just as important as the quality of the songs themselves. Your task is to compute the “best” possible order for them to appear. This shouldn't be too difficult because you are also well versed in the art of programming. For each pair of songs $i$ and $j$ you have assigned a “delight rating” $d_{i,j}$ , which is a positive number indicating how good $j$ sounds when played immediately after $i$ . $d_{i,j}$ and $d_{j,i}$ are generally not equal.

Given $n$ songs, you write a dynamic programming solution for just finding the maximum total delight . Which of the following is a realistic run-time of the algorithm?

Details and Assumptions

• The dynamic programming solution finds an ordering of the songs which maximizes the sum of the "delight rating" of consecutive songs. The actual ordering is not considered.