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

我觉得 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;
    }

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

Note : DP[i][j]表示是否可以使用以 i 结尾的子数组来生成 j！这里我假设 j 也可以是负数。！现在我们可以很容易地导出 sum+ 一个负数 i-1th 位置并将其连接到i thelement 这让我觉得这是一种贪婪的选择（只是因为最大值+元素给了我一个最大值）。

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

编辑：有人说我的算法没有任何意义，所以我试图发布我的代码以使自己清楚。我没有把 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;
}

Output 8

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

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

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

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

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