Both sensor coverage maximization and energy cost minimization are the fundamental requirements in the design of real-life mobile sensing applications, e.g., (1) deploying environ- mental sensors (like CO2, fine particle measurement) on public transports to monitor air pollution, (2) analyzing smartphone embedded sensors (like GPS, accelerometer) to recognize people daily activities. However sensor coverage and energy cost are intuitively contradictory. The higher frequency mobile sensing takes, the more energy is used; and vise versa. In this paper, we design a novel two-step mobile sensing process (“OptiMoS”) to achieve optimal mobile sensing that can effectively balance sensor coverage and energy cost. In the first step, OptiMoS divides the continuous mobile sensor readings into several segments, where the readings in one segment are highly- correlated rather than readings amongst different segments. In the second step, OptiMoS identifies optimal sampling for the sensor readings in each segment, where the selected readings can guarantee reasonably high sensor coverage with limited sampling rate. Various greedy & near-optimal segmentation and sampling methods are designed in OptiMoS, and are evaluated using real- life environmental data from mobile sensors. In this paper, we design a novel two-step mobile sensing process (``OptiMoS'') to achieve optimal mobile sensing that can effectively balance sensor converge and energy cost. In the first step, OptiMoS divides the continuous mobile sensor readings into several segments, where the readings in one segment are highly-correlated rather than readings amongst different segments. %the two neighboring segments, in terms of data modeling. In the second step, OptiMoS identifies optimal sampling for the sensor readings in each segment, where the selected readings can guarantee reasonably high sensor coverage with limited sampling rate. Various greedy \& near-optimal {\em segmentation} and {\em sampling} methods are designed in OptiMoS, and are evaluated using real-life environmental data from mobile sensors.