证明所有前缀和都是非负的
Prove that all prefix sums are non negative
我们有一个包含 n 个整数且总和为非负数的数组。
我需要证明存在一个索引i，使得从i开始，所有前缀和都是非负的，直到我们再次循环到i。
假设数组是a1,a2,a3, ..... , an, 这样 a1 + a2 + a3 + ..... + an>=0。
所以我们需要证明对于某个索引i，所有前缀和都是非负的，即
ai >= 0,
ai + ai+1 >=0,
ai + ai+1 + ai+2 >=0
.
.
ai + ai+1 + ... + an + a1 + .... + ai-1 >=0
我需要这个来回答以下问题，https://www.interviewbit.com/problems/gas-station/。虽然我已经在这个问题的解答中使用了上面的说法，但是我仍然无法证明它。
鉴于您需要证明至少存在 1 个索引 属性 成立的前提，我建议相反的情况成立（即对于每个索引，它至少包含一个前缀sum 为负），然后推导出一个矛盾，即至少有一个索引保持此 属性.
必须为真
假设我们多次重复这个数组，然后构造这个重复数组的前缀和。前缀总和将具有相同的模式，除了每次重复都高出等于数组总和的数量。
考虑前缀和最小的索引x。这将发生在前 n 个样本中（如果数组的总和为正）。
如果你从这个位置 x 开始计算前缀和，那么所有后续的前缀和都将是非负的。
在所有索引对 {j, k} 中，存在一对具有最小（最大负数）sum(j, k) 的此类索引对。设 i = k+1.
如果存在一些序列 a(i), a(i+1), ... a(i+n) 对于 n 不在 {j...k} 范围内使得 sum(i, n) 为负数（即负前缀和），则意味着 sum(j, n) < sum(j, k)，这与我们最初的陈述相矛盾。 （这是真的，因为 sum (j, n) = sum (j, k) + sum (k+1, n) = sum(i, n)，我们称 sum (i, n) 为负。）
如果在 {j...k} 范围内存在一些 n 使得 sum(a, n) 为负，则意味着 sum(k+1, j-1) + sum(j, n) < 0。正如我们所知，总和为正，sum(k+1, j-1) + sum (j, k) > 0（因为它包括所有元素。）因此 sum(j, n) < sum(j, k)，这与我们的初始约束相矛盾。
QED
我们有一个包含 n 个整数且总和为非负数的数组。
我需要证明存在一个索引i，使得从i开始，所有前缀和都是非负的，直到我们再次循环到i。
假设数组是a1,a2,a3, ..... , an, 这样 a1 + a2 + a3 + ..... + an>=0。
所以我们需要证明对于某个索引i，所有前缀和都是非负的，即
ai >= 0,
ai + ai+1 >=0,
ai + ai+1 + ai+2 >=0
.
.
ai + ai+1 + ... + an + a1 + .... + ai-1 >=0
我需要这个来回答以下问题，https://www.interviewbit.com/problems/gas-station/。虽然我已经在这个问题的解答中使用了上面的说法，但是我仍然无法证明它。
鉴于您需要证明至少存在 1 个索引 属性 成立的前提，我建议相反的情况成立（即对于每个索引，它至少包含一个前缀sum 为负），然后推导出一个矛盾，即至少有一个索引保持此 属性.
必须为真假设我们多次重复这个数组，然后构造这个重复数组的前缀和。前缀总和将具有相同的模式，除了每次重复都高出等于数组总和的数量。
考虑前缀和最小的索引x。这将发生在前 n 个样本中（如果数组的总和为正）。
如果你从这个位置 x 开始计算前缀和，那么所有后续的前缀和都将是非负的。
在所有索引对 {j, k} 中，存在一对具有最小（最大负数）sum(j, k) 的此类索引对。设 i = k+1.
如果存在一些序列 a(i), a(i+1), ... a(i+n) 对于 n 不在 {j...k} 范围内使得 sum(i, n) 为负数（即负前缀和），则意味着 sum(j, n) < sum(j, k)，这与我们最初的陈述相矛盾。 （这是真的，因为 sum (j, n) = sum (j, k) + sum (k+1, n) = sum(i, n)，我们称 sum (i, n) 为负。）
如果在 {j...k} 范围内存在一些 n 使得 sum(a, n) 为负，则意味着 sum(k+1, j-1) + sum(j, n) < 0。正如我们所知，总和为正，sum(k+1, j-1) + sum (j, k) > 0（因为它包括所有元素。）因此 sum(j, n) < sum(j, k)，这与我们的初始约束相矛盾。
QED