algorithm - 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; }循环是如果 可以形成带有以 i-1 个 元素结尾的子数组的 j，我可以使用第 i 个元素形成 j+A[i] 并且也可以单独通过启动 a 形成 A[i] 第 i 个位置的子数组最后我们可以在这个 DP 数组中搜索标记为 true 的最大 j!注意:DP[i][j] 表示是否可以使用以 i 结尾的子数组来生成 j!在这里我假设 j 也可以是负数。!现在可以很容易地推导出 sum+ 一个负数 i-1 th 位置并将它与 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 最佳答案 Kadane 是一种迭代动态规划算法。优化迭代DP算法以沿算法进展的主轴移除DP矩阵的一维是很常见的。例如，通常的“最长公共(public)子序列”算法通常用 2D 矩阵来描述，但是如果算法从左到右进行，那么您实际上只需要 2 列的空间。Kadane 的算法是应用于一维问题的类似优化，因此整个 DP 数组消失了。由于某种原因，您问题中的 DP 代码具有 2D 矩阵。我不知道为什么 - 这真的没有意义。这个网站在解释推导方面做得很好:https://hackernoon.com/kadanes-algorithm-explained-50316f4fd8a6关于algorithm - Kadane 的算法是贪心算法还是优化 DP？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/31155269/