怎么证明 LeetCode 134 Gas Station 这个算法的正确性？

[JasonLaw]

对于Gas Station - LeetCode，我也想到了跟 NeetCode 同样的算法，但是我不知道怎么证明算法的正确性。

我有以下疑问：

1. 为什么 sum(gas) >= sum(cost)就表示一定存在那个 starting index ？
2. 怎么证明要找的 starting index 就是 total 一直大于 0 的起点？

对于疑问2，我现在已经理解了，有需要的人可以看一下Arpan Banejee的comment。

对于疑问1，我也理解了，以下视频或许对你有帮助。 https://youtu.be/rf66wlb9aNQ?t=482

[MoYi123]

简单说一下具体是怎么样的算法吧, 不然我还要去看个 15 分钟的视频.

[JasonLaw]

@MoYi123 #1 我希望帮助的人去看一下视频的，这样子才能真正理解那个算法，所以没有贴出代码。

不过还是谢谢啦。

[jdz]

考虑一个数组[a, b, c, d...] 有正有负, 加起来为正数, 与加油站油量 - 消耗量对应. 所以该数组正数对应 加油站油量大于消耗量.
由于数组为正, 必然存在一个最大子数组和为正, 最大子数组左边(如果存在) 连续的数的和必然为小于等于 0, 同理右边 反证法很容易.
以上想清楚了, 一切就很轻松理解了
核心既是 `最大子数组的左边 连续子数组必然小于等于 0, 右边同理`