新题gas station,做出来了却没想通# JobHunting - 待字闺中
s*u
1 楼
看题目就猜到大致类似maximum subarray，用dp做：
for(int i = 0; i < size; i++){
sum += gas[i] - cost[i];
if(subSum > 0)
subSum += gas[i] - cost[i];
else{
subSum = gas[i] - cost[i];
index = i;
}
}
if(sum < 0) return -1;
return index;
但是我自己反而是有点想不通为什么这样就可以。就是说sum >= 0，那肯定有解，但是
既然是环形的，为什么maximum subarray就是这个的解。（大致意思我们都知道，就是
说从一个比较富裕的基础出发，当然是有利的，但是因为是环形，就觉得有点诡异）有
谁能简单证明下么。。
for(int i = 0; i < size; i++){
sum += gas[i] - cost[i];
if(subSum > 0)
subSum += gas[i] - cost[i];
else{
subSum = gas[i] - cost[i];
index = i;
}
}
if(sum < 0) return -1;
return index;
但是我自己反而是有点想不通为什么这样就可以。就是说sum >= 0，那肯定有解，但是
既然是环形的，为什么maximum subarray就是这个的解。（大致意思我们都知道，就是
说从一个比较富裕的基础出发，当然是有利的，但是因为是环形，就觉得有点诡异）有
谁能简单证明下么。。
