algorithm - 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 。这意味着添加任何负索引无助于获得更好的总和，这就是我们可以删除它们的原因!此外，我们关心最大 j 直到第 i-1 个位置并将它与 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 矩阵的一维是非常常见的。

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

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

这个网站很好地解释了推导:https://hackernoon.com/kadanes-algorithm-explained-50316f4fd8a6