Maximum Subarray，为什么要反向循环？

Question

我正在尝试一些分而治之的问题，并遇到了最大子数组“最大子数组问题是在给定的一维数组A [1 ... n中找到具有最大和的连续子数组的任务。 ]的数字”（维基百科）。

我的方法和在线方法之间的唯一区别是：。

[在线解决方案从中间循环到开始，而不是在考虑剩余和时从中间循环。

我想知道为什么会这样吗？我看到的每个解决方案都是这样做的。

下面是GeeksForGeeks的示例。

如果将第一个for循环更改为for i in range(l, mid + 1, 1)（向前循环），那么在测试大输入量时，我将得不到正确答案。

总体而言，我的问题归结为，为什么一个循环向前，而另一个向后？

Answer 1

反向迭代解决了普通（正向）迭代的问题，使得无法修改列表。通过反向迭代，在“当前位置”的任何删除或插入都只会修改您已经看到的列表，而不是您仍需要处理的列表。