c++ - 无法理解算法以找到子数组的最大和

Question

我正在查看用于获取数组中子数组的最大总和的算法，但无法理解代码背后的逻辑。具体来说，这一行 max_ending = max(0, max_ending + number)。我不明白这里正在做什么。另外，这个算法的复杂度是 O(n) 还是 O(n^2)？:

#include <vector>
#include <algorithm>
using namespace std;
template <typename T> T max_sub_array (vector<T> const & numbers)
{
    T max_ending = 0; max_so_far = 0;
    for(auto & number: numbers)
    {
        max_ending = max(0, max_ending + number);
        max_so_far = max(max_so_far, max_ending);
    }
    return max_so_far;
}

谢谢

Answer 1

您提供的算法似乎是(在 Wikipedia 中)Jay Kadane 的算法。 max_ending = max(0, max_ending + number) 这行意味着我们只查看非负和；换句话说，如果向当前子数组再添加一个元素会导致和为负，则使该索引处的最大和 ending 为零(即子数组再次为空)。该线依赖于这样的想法，即我们唯一需要重置检查的子数组窗口的时间是它是否低于零——即使稍后可以添加大的正元素，也可以获得更大的子数组和，而不会在中间下降到负数.让我们看一个例子(max_ending 表示以当前索引结束的子数组的最大和):

           {1,2,23,-4,3,-10}
max_ending  1 3 26 22 25 15
max_so_far  1 3 26 26 26 26

此算法的时间复杂度评估为 O(n)，因为每个数组元素都需要访问一次，并且迭代次数以线性方式取决于数组大小。 O(n^2) 意味着对于每个数组元素，迭代次数将与数组大小成数量级；因此随着数组大小的增加，迭代次数将成二次方增加。