arrays - 给定一个数字数组，找到一个数字开头，使得总和永远不会为负

Question

给定一个整数数组，找到最小的数字 X 开始，这样将数组的元素添加到 X 中，总和总是大于 0

如果给定数组是 {-2, 3, 1, -5} 例如，在上面的数组中，X 应该是 4

解释：如果我们从 4 开始，然后加上第一个数字 -2，数组和变为 4 + (-2) = 2（即 >0） 现在将下一个元素 3 添加到当前和即 2，2+ 3 = 5 （>0）将下一个元素 1 添加到新的总和 5 得到，5 + 1 = 6 （>0）将最后一个元素 -5 添加到新的总和 6 得到 6 + (-5) = 1，这再次更大比零。

给定一个整数数组，如何找到最小的数 X？

标签： arraysalgorithmarray-algorithms

Answer 1

查找给定数组的最小累积和。
需要的结果是1 - MinC

A = [-2, 3, 1, -5]
CSum = 0
MinC = 10000000000
for x in A:
    CSum += x
    MinC = min(MinC, CSum)
Addend = 1 - MinC
print(Addend)

>>> 4