数组中的随机整数.找到连续子集的最大总和

Question

我前面有一个面试问题,我从来没有得到过解决方案.显然,有一种"非常有效"的算法来解决它.

问题:给定一组随机正数和负数,找到总和最大的连续子集.

例:

[1, -7, 4, 5, -1, 5]

这里最好的子集是 {4, 5, -1, 5}

我认为没有解决办法,只有蛮力方法.什么是有效的方法？

Answer 1

将列表转换为累积和列表，[1,-7,4,5,-1,5] to [1, -6, -2, -3, 2]。然后遍历累积和列表，保存迄今为止的最小值以及您看到的当前值与当前最小值之间的最大差值。从这里得到的