Better with Age (Or Not)
You and your roommates, all at least 21 years of age, have gotten hooked brewing your own beer from kits. You've made quite a few batches, each from a different mix, so you now have an impressively varied range of flavors; summer cherry wheat, chocolate hazelnut lager, pepperoni pale ale, etc. You'd like to get through all the batches before your court-mandated AA meetings are set to begin. You can probably polish off a batch a day, but some batches are clearly better than others, and you can't decide in which order to drink them. Further complicating matters, each beer is aging, causing it's quality to change over time. Sometimes, like a good wine, this change is for the better. Other times, as in the case of the pepperoni pale ale, each day you wait makes it that much more likely to kill you. Of course, you're not willing to throw anything out, so you've got a little optimizin' to do.
To make things concrete, you have n batches of beer, which you'd like to drink over the next n days, one batch per day. Each batch i has an initial quality qi and a rate of change ri, indicating how much that quality changes each day. So if you drink beer i after d days, the value you'll get is qi + d. ri. Your goal is to maximize the sum of these values over all n beers. Keep in mind that ri may be negative for some i, but you still intend to consume all the beer in n days, even if the value for some beers is negative.
Give an algorithm to solve this problem, and prove it is correct.