Programming by example (PBE) is an important subproblem of program synthesis and the techniques of PBE have been applied to many domains. Though many techniques for accelerating PBE systems have been explored, the scalability remains one of the main challenges: there is still a gap between the performances of state-of-the-art synthesizers and the industrial requirement. To further speed up solving PBE tasks, in this paper we propose a novel PBE framework MaxFlash, which uses the naturalness of programs to guide a search based on dynamic programming, such that the search will focus on subproblems that form more natural programs, and avoid unnatural programs. Our evaluation shows that MaxFlash achieves $\times 5.097- \times 2321$ speed-ups against state-of-the-art solvers on $244$ real-world tasks.