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

Question

我感觉Kadane的算法是最大子数组真动态规划解法的修改版problem.Why我感觉是这样吗？我感觉是因为计算最大子数组的方式可以采取：

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 个元素并通过在第 i 个位置开始一个子数组单独形成 A[i] 最后我们可以在这个 DP 数组中搜索标记为 true 的最大值 j！

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

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

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

我认为很难说这个算法到底是什么。
但是大部分书都把这个算法归类在DP部分，因为你结合了dp[n-1]的解来为dp[n]求解。

注意：我不明白你为什么使用这个版本的算法O(n^2) 您可以将此算法简化为 O(n)

curmax=0
sol=0
for x in array
    curmax+=a[x]
    if(curmax<0)curmax=0
    if(curmax>sol)sol=curmax

Answer 2

我认为这是一个贪心算法，因为kadanes算法在每一步找到最大和然后找到整体解决方案。

Answer 3

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

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

例如，通常的'longest common subsequence'算法通常用二维矩阵描述，但如果算法从左到右进行，那么您实际上只需要space 2列。

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

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

Answer 4

正如算法导论中所定义的，“贪心算法总是做出当前看起来最好的选择。也就是说，它会做出局部最优选择，希望此选择将导致全局最优解。"

Kadane 的算法确实通过 current_sum = max(0, current_sum + x) 寻找局部最优解；同时，这也可以看作是 space 优化的动态规划解决方案 - dp[i] 仅依赖于 dp[i-1] 因此我们使用整数变量来保存 space。

所以我觉得DP的转换函数恰好是贪心的，看起来既是DP又是贪心的

Answer 5

Kadane 的算法既可以看作是贪心算法，也可以看作是 DP。如我们所见，我们保留了运行个整数和，当它小于 0 时，我们将其重置为 0（贪心部分）。这是因为继续使用负和比使用新范围重新开始更糟糕。现在它也可以看作是一个 DP，在每个阶段我们有 2 个选择：要么获取当前元素并继续之前的总和，要么重新开始一个新的范围。这两个选择都在实施中得到了照顾。

贪婪索尔

# Python program to find maximum contiguous subarray
  
# Function to find the maximum contiguous subarray
from sys import maxint
def maxSubArraySum(a,size):
      
    max_so_far = -maxint - 1
    max_ending_here = 0
      
    for i in range(0, size):
        max_ending_here = max_ending_here + a[i]
        if (max_so_far < max_ending_here):
            max_so_far = max_ending_here
 
        if max_ending_here < 0:
            max_ending_here = 0  
    return max_so_far
  
# Driver function to check the above function
a = [-13, -3, -25, -20, -3, -16, -23, -12, -5, -22, -15, -4, -7]
print "Maximum contiguous sum is", maxSubArraySum(a,len(a))

DP 太阳系

# Python program to print largest contiguous array sum
 
from sys import maxsize
 
# Function to find the maximum contiguous subarray
# and print its starting and end index
def maxSubArraySum(a,size):
 
    max_so_far = -maxsize - 1
    max_ending_here = 0
    start = 0
    end = 0
    s = 0
 
    for i in range(0,size):
 
        max_ending_here += a[i]
 
        if max_so_far < max_ending_here:
            max_so_far = max_ending_here
            start = s
            end = i
 
        if max_ending_here < 0:
            max_ending_here = 0
            s = i+1
 
    print ("Maximum contiguous sum is %d"%(max_so_far))
    print ("Starting Index %d"%(start))
    print ("Ending Index %d"%(end))
 
# Driver program to test maxSubArraySum
a = [-2, -3, 4, -1, -2, 1, 5, -3]
maxSubArraySum(a,len(a))

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

Is Kadane's Algorithm Greedy or Optimised DP?

algorithm

dynamic-programming

greedy