134. Gas Station

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.

我又回来了 四天半的研究生建模 差点没累死我。把断更的补上吧，接着写。

问题是问你从哪个起点开始好，可以先把两个数组转换成一个，这样可以清楚地表示我在这个点是得到还是失去，那么我该从那个点开始呢？

是最大的点吗？ 不，不一定假如我在这个点最大例如8，那么下一个点的损失可能比他还大例如-9，显然没有那么简单.那么什么情况才能算是最好的呢？

明显的我们需要这样一个起点，从这个起点开始他的和一直是正的，并且这个和在所有连续的子数组里面是最大的，如果从这样的结点出发还不能得到一个我们想要的结果，那么明显是不可能的了。于是问题化简为了数组的最大连续子数组的和的问题。

显然只有当我们的子数组之和小于零了，才需要更换起点注意 如果到了队尾 且数组的总和大于零起点就是题目要求的起点。

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int[] dif = new int[gas.length];
        for(int i =0 ;i<gas.length;i++)
               dif[i]=gas[i]-cost[i];
        int start = 0 ;
        int max = Integer.MIN_VALUE;
        int val = 0;
        int sum = 0;
        for(int i = 0 ;i<gas.length;i++)
        {
            sum+=dif[i];
            val+=dif[i];
            if(val>max)
            {
                max=val;
               
            }
            if(val<0)
            {
                val=0;
                if(i+1==gas.length)
                    break;
                start=i+1;
                // now recount ;
            }
        }
        if(sum<0)
            return -1;
        else
            return start;
            
    }
}