动态编程算法(KADANE)

Question

算法的描述：最大子阵列问题给定n个实数a（1）…A（n）的序列，确定一个连续的子序列a（i）...

算法：

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％精确的，算法实际计算的是： non-eppribly 子序列的最大总和，对于 nontempenty 数组（对于空数组而言为零，这有些不一致）。这对所有数字均为负数的数组有所不同 - 如果我们将空序列计为有效，则结果应为0。算法会产生最大的负数，而不是为0。

证明：

在循环的开头new_sum始终是结束（排除） a[i]的序列的最大总和（因此，i>0最多可a[i-1]，0对于i==0）。通过诱导循环执行来证明。对于i=0（new_sum == 0）显然是正确的，这是一个空序列的总和），并且在分配后对于i+1而变得正确，因为最大的和非空的序列在a[i]结束（这是a[i+1]之前的最后一个元素）包括a[i]，因此是a[i]本身的最大值以及a[i]的总和和前一个序列。

overall_sum只是a[i]的所有new_sum值的最大值，因此代表了最大的全局子序列（对于某些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-1]中的A[i]，那么A[i]包括上一节是没有意义的，我们从头开始计数。这确保了我们从A[i]开始计算的总和达到最大的总和。我们可能会看到它减少了，但是到那时，我们已经更新了总的总和。