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;
}
}
