Try*_*ing 14 java arrays algorithm
我们都知道最大和子阵列和着名的Kadane算法.但是我们可以使用相同的算法来找到最小总和吗？
我的看法是:
改变符号并找到最大总和,与我们计算最大总和子阵列的方式相同.然后更改数组中元素的符号以使其处于初始状态.
如果有任何问题,请帮我纠正算法.
极端情况:我知道如果所有元素都是正数就会出现问题,我们可以通过执行一些预处理来处理这种情况,即如果所有元素都是+ ve,则遍历数组,而不是仅返回数组中的最小数字.
上面提到的算法将起作用并由dasblinkenlight很好地支持(解释).
我提到的方法是否能找到最小的总和？
是的,它会的.您可以重新说明找到最小和的问题,即找到具有最大绝对值的负和.当你切换数字的符号并保持算法的其余部分时,这就是算法将返回给你的数字.
我知道如果所有要素都是积极的,那么就会出现问题
不,没有问题:当所有元素都是负数时,考虑原始的Kadane算法.在这种情况下,算法返回一个零序的空序列 - 在这种情况下可能的最高值.换句话说,当所有元素都是负数时,最好的解决方案是不使用它们.
如果所有数字都是正数,您修改后的算法也将采用相同的方法:再次,您最好的解决方案是根本不采用数字.
如果添加一个要求,即从算法返回的范围可能不为空,则可以稍微修改算法以找到最小的正数(或最大的负数),以防Kadane的算法返回空范围作为最佳解决方案.