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.hild.

我的提交：

/*17.3.31
*有点像最大连续子序列和的动态规划解法
*如果total大于0，从左到右扫描，一定能切分出一个和大于0的区间（起点为i,终点为数组的结尾）
*如-1，-2，2，3，-6，10
*-1被切开，-2被切开，3，4，-6被切开，10大于0，所以以10为起点！
*换一个顺序-6，10，-1，-2，2，3
*-6被切开，10~3大于0，结果还是以10为起点。
*/
public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int start = 0,total = 0;
        for(int i=0,tank=0;i<gas.length;i++){
            if(tank<0){
                tank = gas[i] - cost[i];
                start = i;
            }
            else{
                tank += gas[i] - cost[i];
            }
            total += gas[i] - cost[i];
        }
        return total<0?-1:start;
    }
}