Divide and conquer algorithm for a gas station problem
You can use binary search on the range of the car. Refill only if needed.

Here is the algorithm in more detail.

Let low = 0 and high = distance from c0 to cn. During the whole algorithm, range high is always big enough for a car to reach cn from c0, while range low is always not. 
Repeat the following as long as low + 1 &lt; high

mid = (low + high) /2
If range mid is big enough, set high = mid. Otherwise, set low = mid.


Return high, which must be the minimum range of the car.


How can we check if a given range is big enough?
Simple.
We will try driving a car with that range from c0 to cn. At each city, if the remaining range of the car is not enough for the car to reach the next city, refill the car to its full range. If we have refilled s+1 times before we have reached cn, that given range is not enough. Otherwise, it is enough.

It takes $O(n)$ time to check whether a given range is big enough.
The bisecting loop will run at most $\lceil\log_2 m\rceil$ iterations, where $m$ is the distance from c0 to cn.
So, the algorithm runs in $O(n\log_2 m)$-time.