find the subvector with max sum in a circular array

input: a circular array
output: a subvector of the array that has max sum

We can think that n elements are put on a circle and we want to find the subvector from the circle that has max sum.


Solution:
1. take any element as the leader and break the circle into one dimensional array a[1:n]. use the classical method to get the maxsum subvector
2. we did not consider the case that the maxsum subvector in the circle passes a[1]. in the next step we will figure out the maxsum subvector that passes a[1], suppose it is a[n - i:j].
3. claim: a[j+1:n-i-1] is the minsum subvector of a[1:n]. because sum of a[j+1:n-i-1] + sum of a[j+1:n-i-1] is fixed, one takes max means the other gets min.


Application:
find an index that the subvector starting from him always has sum greater than or equal to 0.


There are n gas stations posit... | CareerCup: "Bloomberg LP » Brain Teasers
DPS Prog on May 17, 2009 | Question #134799 (Report Dup) | Edit | History

There are n gas stations positioned along a circular road. Each has a limited supply of gas. You can only drive clockwise around the road. You start with zero gas. Knowing how much gas you need to get from each gas station to the next and how much gas you can get at each station, design an algorithm to find the gas station you need to start at to get all the way around the circle.
More Questions from this Interview
Filed Under: Bloomberg LP » Brain Teasers » Software Engineer / Developer


LOler on May 18, 2009 |Edit | Edit

O(n^2) time is easy. Start at each and just simulate it out.

O(n) time is possible, but I won''t spoil it for you.
Reply to Comment
CyberPhoenix on May 19, 2009 |Edit | Edit

Check Cormen for this, Its in exercise section of some chapters.....
Reply to Comment
Cookie on May 20, 2009 |Edit | Edit

Here is what Cormen has to say about the above problem but i quite well did not understand the solution..

The optimal strategy is the obvious greedy one. Starting will a full tank of gas,
Professor Midas should go to the farthest gas station he can get to within n miles
of Newark. Fill up there. Then go to the farthest gas station he can get to within n
miles of where he Þlled up, and Þll up there, and so on.
Looked at another way, at each gas station, Professor Midas should check whether
he can make it to the next gas station without stopping at this one. If he can, skip
this one. If he cannot, then Þll up. Professor Midas doesn’t need to know how
much gas he has or how far the next station is to implement this approach, since at
each Þllup, he can determine which is the next station at which he’ll need to stop.
This problem has optimal substructure. Suppose there are m possible gas stations.
Consider an optimal solution with s stations and whose Þrst stop is at the kth gas
station. Then the rest of the optimal solution must be an optimal solution to the
subproblem of the remaining m − k stations. Otherwise, if there were a better
solution to the subproblem, i.e., one with fewer than s −1 stops, we could use it to
come up with a solution with fewer than s stops for the full problem, contradicting
our supposition of optimality.
This problem also has the greedy-choice property. Suppose there are k gas stations
beyond the start that are within n miles of the start. The greedy solution chooses
the kth station as its Þrst stop. No station beyond the kth works as a Þrst stop,
since Professor Midas runs out of gas Þrst. If a solution chooses a station j < k as
its Þrst stop, then Professor Midas could choose the kth station instead, having at
least as much gas when he leaves the kth station as if he’d chosen the j th station.
Therefore, he would get at least as far without Þlling up again if he had chosen the
kth station.
If there are m gas stations on the map, Midas needs to inspect each one just once.
The running time is O(m).
Reply to Comment
Marian on May 26, 2009 |Edit | Edit

Cookie, no, that's not the problem. Therefore that's not the solution :))

I won't give the full solution how to do it in O(n), but I will provide all the hints.
The problem can be cast into a modified version of the very know problem: Maximum Consecutive Subsequence (of length 2*n-1). If during the search (in linear time for Maximum Consecutive Subsequence) you find a positive sum of length n, you found the solution to this problem.
Reply to Comment
karthikvaidy on June 12, 2009 |Edit | Edit

For each station, find (distance that can be traveled with gas available in that station - distance to next station). Create an array of these values and find the maximum positive consecutive substring. You have to start driving at the beginning of this substring.
PS: Remember that the stations are circularly arranged, so should the array. So it is possible for you to start on the 'last' station and still go around to all of them.
PPS: Another thing that can be done is to ensure that sum of all distances to be traveled is less than distance that can be traveled with available gas. Otherwise, it makes not difference where you start, you will get stranded.
Reply to Comment
Bajanfella on June 14, 2009 |Edit | Edit

Basically you have two arrays, gas_needed[n] and gas_at_station[n]. However, I would work with a third array which is the difference gas_needed - gas_at_station. Let's call this array gas_remaining[n](R[n])
Sum(Ri) where m is the nth consecutive station after i. i is the starting station if
i->m
the sum never goes negative.

O(m)
Reply to Comment
noname on July 10, 2009 |Edit | Edit

Bajanfella, Your algorithm is O(m^2) instead of O(m). Basically, you are just simulating with different starting points.
Reply to Comment
smartAss on July 17, 2009 |Edit | Edit

making use of a part of data str given by BajanFella, Lets take all the three arrays. Now in the arrya gas_remaining[] find the maximum subsequence which can be done in O(m), now starting at the first element of the subsequence solves the problem, thats it, we're done...
Reply to Comment
googler on August 13, 2009 |Edit | Edit

bejafella's answer is the correct one...and I must say this quite a popular interview question!
Reply to Comment
john on August 19, 2009 |Edit | Edit

yes, bejafella's got it
Reply to Comment
vipul k. on September 21, 2009 |Edit | Edit

if i have a car with 'zero' gas, how would i start the car in the first place???
Reply to Comment
S.M on October 01, 2009 |Edit | Edit

What if the gas tank is limited in capacity ?"