动态编程算法（Kadane）

Question

算法描述：最大子阵列问题给定n个实数A（1）... A（n）的序列，确定子序列中元素之和最大化的连续子序列A（i）... A（j）。

算法：

int kadane(int a[], int n)
{
    int overall_sum=0;  //overall maximum subarray sum
    int new_sum=0;      //sum obtained by including the current element

    for(int i=0;i<n;i++)
    {
        //new_sum is the maximum value out of current element or the sum of current element
        //and the previous sum
        new_sum=max(a[i], new_sum+a[i]);
        cout << new_sum << " : ";
        //if the calculated value of new_sum is greater than the overall sum,
        //it replaces the overall sum value
        overall_sum=max(overall_sum, new_sum);
        cout << overall_sum << endl;
    }

    return overall_sum;

}

我知道我们正试图将问题分解为小的子问题。该想法是确定n-1子序列的最大部分和以找到n序列的最大部分和。代码看起来很清楚，因为我可以在纸上找到解决方案，但这个想法看起来很神奇。有人能提供更好的解释吗？或证明其工作原理？

Answer 1

为了100％精确，算法实际计算的是：非空子序列的最大总和，对于非空数组（对于空数组为零，这有点不一致）。它对所有数字都为负数的数组产生影响 - 如果我们将空序列计为有效，那么结果应为0.对于这种情况，算法产生最大的负数而不是0。

证明：

在循环开始时，new_sum总是那些以（不包括）a[i]结束的序列的最大总和（因此，a[i-1]的i>0，0的i==0）。通过诱导循环执行来证明。这显然适用于i=0（new_sum == 0，它是空序列的总和），并且在赋值后变为i+1，因为在a[i]（这是a[i+1]之前的最后一个元素）结束的最大和非空序列需要包括a[i]，因此是a[i]本身的最大值和a[i]和前面序列的总和。

overall_sum只是new_sum所有a[i]值的最大值，因此代表了最大的全局子序列（对于某些i，它必须以a[i]结束，因此最大化所有a[i]作品）。

Answer 2

您已经在代码注释中包含了解其原因的解释：

new_sum is the maximum value out of current element
or the sum of current element and the previous sum

而不是将算法视为元素i的最佳总和，而不是将其视为从元素i开始的最佳总和。

请注意，该算法不允许new_sum在遍历中不包含当前元素。如果A[i]单独加上A[i]加到加总到A[i-1]，那么A[i]包含前一部分就没有意义了，我们从头开始计算。这保证了我们从A[i]开始计算的总和达到了它可以达到的最大值。我们可能会看到它减少但到那时我们已经根据需要更新了总体最大值。