Gas Station

Q;
There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
Note:
The solution is guaranteed to be unique.
A:    解法二更简单明了~~~~~~~更深入核心~~~~~~




-----------------------------------------第二遍----------------------------

“假设，我们从环上取一个区间[i, j], j>i， 然后对于这个区间的diff加和，定义
sum[i,j] = ∑diff[k] where i<=k<j
如果sum[i,j]小于0，那么这个起点肯定不会在[i,j]这个区间里，跟第一个问题的原理一样。举个例子，假设i是[0,n]的解，那么我们知道 任意sum[k,i-1] (0<=k<i-1) 肯定是小于0的，否则解就应该是k。同理，sum[i,n]一定是大于0的，否则，解就不应该是i，而是i和n之间的某个点。所以第二题的答案，其实就是 在0到n之间，找到第一个连续子序列（这个子序列的长度必然是n）大于0的。   ”

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        int A[2*n];
        for(int i =0;i<n;i++)
            A[i]=A[i+n] = gas[i] -cost[i];
        
        int presum = 0;
        for(int i = 0;i<2*n; ++i) // calculate the accumulated gas so far
        {
            A[i] += presum;
            presum = max(0,A[i]);
        }
        
        int count = 0;// count values that >=0
        for(int i =0;i<2*n;++i)
        {
            count = A[i]>=0?count+1:0;
            if(count==n)
                return i-count+1;
        }
        return -1;
    }
};

 -------------------------------------------3 rd ----------------------------------------
这次， 第二遍是利用了extra array,  this time, we do not need extra array 
这一遍，自己是  寻找max sub array, （with size <= n)， 然后记录下来。再去查看是否能跑完。

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int start = 0;
        while(start<n){
            int end = start;// end is exclusive
            int sum = 0;
            while(sum >=0&& end-start < n){
                sum += gas[end%n] - cost[end%n] ;
                end ++;
            }
            if(sum<0)
                start = end;
            else
                return start;
        }
        return -1;
    }
}

 -------------------------------------------1 st ----------------------------------------
思路很简单， 就是CLRS chapter 4 的那个divide-and-conquer 思路。
稍微tricky的一点儿就是，把dif数组double了长度， 这样就避免了circle问题。

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
            // this problem is quite like that of finding the max-subarray.
            int n = gas.length;
            int[] dif = new int[2*n];
            for(int i =0;i<n;i++){
                dif[i] = gas[i] - cost[i];
                dif[n+i] = dif[i];
            }
            // find the max-sub array of the diff
            int[] arraIndexNSum = maxSubArray(dif,0,2*n-1);
            // test if we can traver all the circle
            int startIndex = arraIndexNSum[0];
            int sum =0;
            for( int i = startIndex;i<startIndex+n;i++){
                sum+=dif[i];
                if(sum<0){
                    return -1;
                }
            }
            return startIndex;
            
        }
        private int[] maxSubArray(int[] dif,int low, int high){
            // return the subarray index within which it has the max-sum
            if(high == low){
                int[] tmp = {low,high,dif[low]};
                return tmp;
            }
            // now  hig > low
            int mid = (low+high)/2;
            int[] left = maxSubArray(dif,low,mid);
            int[] right = maxSubArray(dif,mid+1,high);
            int[] cross = findMaxAcross(dif,low,mid,high);
            if(left[2] >= right[2] && left[2]>=cross[2]){
                return left;
            }else if(right[2] >= left[2] && right[2]>=cross[2]){
                return right;
            }else{
                return cross;
            }
        }
        private int[] findMaxAcross(int[] dif, int low,int mid, int high){
            // because that all solution is unique, we do not need to consider the case that they are 
            int leftSum = Integer.MIN_VALUE /2 -1;
            int sum =0;
            int maxLeft = mid;
            for(int i = mid ; i>=low ;i--){
                sum += dif[i];
                if(sum>leftSum){
                    leftSum = sum;
                    maxLeft = i;
                }
            }
            int rightSum = Integer.MIN_VALUE /2 -1;
            int length = dif.length/2;
            int maxRight = mid+1;
            sum = 0;
            for(int i=mid+1; i<high && (i-maxLeft+1)<=length; i++){
                sum += dif[i];
                if(sum> rightSum){
                    rightSum = sum;
                    maxRight = i;
                }
            }
            int[] tmp =  {maxLeft,maxRight,leftSum+rightSum};
            return tmp;
        }
        
    }

注意，这里，有一点儿其实是不太对的， 就是，利用了unique solution的情况。 导致了，我们在fincMaxAcroos的时候，不分左右，直接就在右边寻找的时候，限制了长度。
Mistakes:
1:在 findMaxAcross（） 中，由于我们开始让
int leftSum = Integer.MIN_VALUE ；
int rightSum = Integer.MIN_VALUE  那么，在二者没有动的时候，两者相加，就得到一个很大, 正的 int数组。 --------------- 因此， 实际代码中，我们用
int leftSum = Integer.MIN_VALUE /2 -1;来代替。

2：   其实，要求max sum subarray， 有个更简单的算法， 也是O(n)的。  看本博客的帖子。

Learned: