An explicit solution of an infinite horizon optimal stopping problem for a Levy process with a nonmonotonic reward function is given, in terms of the overall supremum of the process, when the solution of the problem is one-sided. The results are obtained via the consideration of the generalized averaging function associated with the problem. The method, initially tailored to handle polynomial rewards, has a wide range of applications, as shown in the examples: optimal stopping problems for general polynomial rewards of degree two and three for spectrally negative processes, a quartic polynomial reward and Kou's process, a portfolio of call options, and a trigonometric payoff function. These last two examples are given for general Levy processes.