我提到的方法是否可以找到最低金额?
是的,它会的。您可以将找到最小总和的问题重述为找到具有最大绝对值的负和的问题。当您切换数字符号并保持算法的其余部分不变时,这就是算法将返回给您的数字。
我知道如果所有要素都是积极的问题
不,没有问题:当所有元素均为负数时,请考虑原始的Kadane算法。在这种情况下,算法将返回一个空序列,该序列的总和为零(在这种情况下,最高数为零)。换句话说,当所有要素均为负数时,最好的解决方案是不采用任何要素。
如果所有数字均为正数,则修改后的算法将执行相同的操作:同样,最好的解决方案是根本不使用数字。
如果您添加了从算法返回的范围不能为空的要求,则可以稍加修改算法,以找到最小的正数(或最大的负数),以防Kadane的算法返回空范围作为最佳解决方案。



