Energy inefficiency is an influential non-functional issue for smartphone applications, causing increased concerns from users. Locating these problems is labor-intensive, thus automated diagnosis tools are in demand. Some existing approaches detect energy inefficiency problems by exploring application states with the JPF framework, and get favorable results. However, the effects of these approaches are restricted because of their imprecise application execution models and incomplete energy inefficiency patterns. This paper introduces NavyDroid, an effective and efficient tool of energy inefficiency problem diagnosis for Android applications. We constructed a comprehensive application execution model in the form of a state machine, which accurately simulates the runtime behavior of Android applications. We designed a parallel algorithm to systematically explore an application’s state space. Our approach supports more energy inefficiency patterns, and is able to detect complicated wake lock misuses. We implemented our approach as a prototype tool and applied it to real-world applications. We evaluated NavyDroid with 19 real-world Android applications, and NavyDroid located more energy inefficiency bugs in these applications than the existing work E-GreenDroid did. Also, NavyDroid reduced the analysis time with its parallel state exploration algorithm. The experimental results demonstrated the effectiveness and efficiency of our approach for detecting energy inefficiency bugs in Android applications.