I am about to take part in a dance contest and tomorrow is the big day! I know apriori the list with the n songs of the contest and their order. After much scouting, I was able to determine the judges and my skills so good that I can accurately predict my result if I dance the i-th song of the list, i.e. score(i).
However, after the i-th song, I need time to rest, namely I cannot dance the next rest(i) songs, i.e. songs i + 1, ..., i + rest(i). No other constraint exists for the number of songs I can dance. Give an effective algorithm for computing your ideally maximum total score and its complexity.
So I think that recursion should be used, where max(i) = max(i + 1) or max(i) = score(i) + max(i + 1 + rest(i)) and then pick the best out of this two at every step. Can someone help?
Let there be n songs indexed 0..n-1. Let Opt(i) be the maximum total score given that we're free to dance starting on song i. The recurrence for Opt is
Opt(n) = 0
Opt(i) = max(Opt(i+1),
Score(i) + Opt(i + 1 + Rest(i))) for i = 0..n-1.
Intuitively, we either don't dance song i and get the value of the remaining time, or we do, score song i, rest, and get the value of the time after resting.
This recurrence should be evaluated for i descending, with the previously calculated values cached in an array. The running time is O(n).