arrays - 证明所有前缀和都是非负的

<分区>

我们有一个包含 n 个整数的数组，其总和为非负数。

我需要证明存在一个索引i，使得从i开始，所有前缀和都是非负的，直到我们再次循环到达i。

假设数组是a₁, a₂, a₃, ..... , a_n，这样 a₁ + a₂ + a₃ + ..... + a_n>=0。

所以我们需要证明对于某个索引i，所有前缀和都是非负的，即
a_i>= 0,
a_i + a_i+1>=0,
a_i + a_i+1 + a_i+2>=0
.
.
a_i + a_i+1 + ... + a_n + a₁ + ... + a_i-1>=0

我需要这个来回答以下问题，https://www.interviewbit.com/problems/gas-station/ .虽然我已经在这个问题的解决方案中使用了上面的说法，但我仍然无法证明它。

最佳答案

假设我们多次重复这个数组，然后构造这个重复数组的前缀和。前缀总和将具有相同的模式，除了每次重复都高出等于数组总和的量。

考虑前缀和最小的索引x。这将发生在前 n 个样本中(如果数组的总和为正)。

如果你从这个位置 x 开始计算前缀和，那么所有后续的前缀和都将是非负的。

关于arrays - 证明所有前缀和都是非负的，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37345579/

相关文章：

php - 特定邮政编码 : PHP mysql 附近的用户