Kadane 的算法是贪心算法还是优化 DP？

Question

我觉得Kadane的算法是最大子数组问题的真正动态规划解决方案的修改版本。为什么我会这么觉得？我觉得是因为计算最大子数组的方法可以采用：

for(i=0;i<N;i++)
    {
        DP[i][A[i]]=true;
        for(j= -ve maximum ;j<= +ve maximum ;j++)
        if(DP[i-1][j])
            DP[i][j+A[i]]=true;
    }

递归是如果可以用一个以 i-1 个元素结尾的子数组来形成j，我可以使用第 i 个元素形成j+A[i]并且也可以通过在第 i 个位置开始一个子阵列来单独形成A[i]并且最后我们可以在这个 DP 数组中搜索标记为 true 的最大 j！

注意：DP[i][j]表示是否可以使用以 i 结尾的子数组来生成 j！在这里我假设 j 也可以是负数。！现在可以很容易地推导出 sum+ 一个负数 < sum 。这意味着添加任何负指数无助于获得更好的总和，这就是我们可以放弃它们的原因！Morover 我们关心直到i-1th 位置的最大 j并将它与i th 元素连接起来，这让我觉得这是一种贪婪的选择（只是因为最大值 + 元素给了我一个最大值）。

注意：我现在还没有研究过贪婪算法，但我知道什么是贪婪的选择！

编辑：有人说我的算法没有任何意义，所以我试图发布我的代码以使自己清楚。我没有把 j 当作 -ve，因为它们没有成果。我重复我的状态被定义为是否可以使用以 i 结尾的子数组来生成 j。

#include<bits/stdc++.h>
using namespace std;
int DP[101][101];
int main()
{
    int i,j,ans=INT_MIN;
    int A[]={3,-1,2,-1,5,-3};
    int N=sizeof(A)/sizeof(int);
    for(i=1;i<=N;i++)
    {
        if(A[i-1]>=0)
            DP[i][A[i-1]]++;
        for(j=0;j<=100;j++)
        {
            if(DP[i-1][j])
            {
                if(j+A[i-1]>=0)
                    DP[i][j+A[i-1]]++;
            }
            if(DP[i][j])
                ans=max(ans,j);
        }
    }
    cout<<ans<<"\n";
    return 0;
}

输出 8

Answer 1

Kadane 是一种迭代动态规划算法。

优化迭代DP算法以沿算法进展的主轴移除DP矩阵的一维是很常见的。

例如，通常的“最长公共子序列”算法通常用 2D 矩阵来描述，但是如果算法从左到右进行，那么您实际上只需要 2 列的空间。

Kadane 的算法是应用于一维问题的类似优化，因此整个 DP 数组消失了。由于某种原因，您问题中的 DP 代码具有 2D 矩阵。我不知道为什么 - 这真的没有意义。

这个网站在解释推导方面做得很好：https : //hackernoon.com/kadanes-algorithm-explained-50316f4fd8a6