During review, I found a superior solution. What now? I received a journal paper for a review. The paper suggests a solution to an important problem, but the solution is very complicated and has mediocre performance. While reading the paper, I thought of a different solution, which is much simpler and has better performance (to give some scale: their solution is 1 page to write and 5 pages to prove; my solution is 5 lines to write and half a page to prove).

What should I do now?

A. Write my solution in the review, hoping the authors will remember to "thank the anonymous reviewer"?

B. Recommend that the paper published as is, then write a paper of my own with my improved solution?

C. Something else?

EDIT: Before I found the superior solution, I thought of recommending "resubmit with major revision", with the reasons that I mentioned above: your solution is too complicated and its performance is too weak.

However, now I am not sure it is the good course of action. A major revision may take a long time. The authors might even decide to delay or stop working on the paper without telling the editor (or me). Meanwhile, I will have to postpone the publishing of the superior solution for an indefinite amount of time. What do you think?
I didn't get a clear impression of your opinion of the authors' work.  "Solving an important problem" ought to make for an excellent paper, but the rest of your description seems to partially negate that.  (In particular, I don't quite know what a "nonstandard input parameter" is, but it sounds a bit like they are cheating or that the legitimacy of their solution could be a matter of debate.)  

Either way, it seems to follow from what you say that you feel that you have solved an important problem, indeed in a better way than the authors.  Unless you are such a known superstar in your field that this is a commonplace occurrence for you, I would think that you deserve to get more out of this than an anonymous thanks.  To me the options seem to be:

1) If the authors' paper is strong enough to be published, say so.  You should not hide your opinions about their shortcomings, but you don't have to include your new ideas in your referee report.  Then:

1a) If just by responding to your criticism (if they care to) the authors replicate your better solution, then it seems that you did not add critical value, and I would just recommend accepting their modified version and letting the matter end there.  

But

1b) If your conscientious refereeing produces a version that is worth publishing but does not replicate your superior solution, then you should prepare your solution for publication.  The timing of this is something that you should ask for other opinions about.  It would be ideal if the authors had circulated their results in preprint form.  If not, you may need to delay submission until their paper actually appears.

2) If you think the paper is not publishable in its current form in the journal to which it was submitted but that it inspired you to solve the problem in a better way, this may be a case for you to ask permission to contact the authors and add your work to theirs.  

3) If the work is really not valuable and your solution has little or nothing to do with theirs, then you could just recommend the paper for rejection and then submit your own solution elsewhere.  Examine your conscience carefully before doing this though: imagine that the authors found out exactly what you did.  Would they see it your way?