Kadane的算法是贪婪的还是优化的DP? [英] Is Kadane's Algorithm Greedy or Optimised DP?

问题描述

我觉得Kadane的算法是最大子数组问题的真正动态编程解决方案的修改版本，为什么会这样呢?我觉得因为可以通过以下方式来计算最大子数组的方法:

I feel like Kadane's algorithm is a modified version of the true dynamic programming solution of maximum subarray problem.Why do I feel so? I feel because the way to calculate the maximum subarray can be taken by:

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！

The recurrence being if it is possible to form j with a subarray ending at i-1 elements i can form j+A[i] using the i th element and also form A[i] alone by starting a subarray at i th position And at last we can search this DP array for maximum j that is marked true!

注意: DP [i] [j] 表示是否有可能使用以i结尾的子数组制作j！在这里，我假设j也可以为负.现在，可以很容易地得出该和+负数＜.总和.这意味着添加任何负索引将无助于获得更好的总和，这就是我们为什么可以降低它们的原因！Morover我们关心最大j直到第 i-1 个位置，并将其与 i th 元素联系起来，这让我感到这是一种贪婪的选择(只是因为max+元素给了我最大的价值.

Note : DP[i][j] represents if it is possible to make j using a sub array ending at i! Here I assume j can be negative too.! Now one can easily derive that sum+ a negative number < sum . That implies adding any negative indices wont help getting a better sum thats why we can drop them! Morover we care about the maximum j till i-1 th position and connect it with i th element which makes me feel it is kind of making a greedy choice ( Just because maximum + element gives me a maximum).

注意:到目前为止，我还没有研究过贪婪算法，但是我知道贪婪的选择是什么！

NOTE: I haven't studied Greedy algorithms by now but I have an idea what a greedy choice is!

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

SOmeone said my algorithm doesn't makes any sense so I am trying to post my code to make myself clear. I haven't taken j as -ve as they aren't fruitful. I repeat my state is defined as is it possible to make j using a subarray ending at i.

#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's是一种迭代的动态编程算法.

Kadane's is an iterative dynamic programming algorithm.

优化迭代DP算法以沿算法进程的主轴移除DP矩阵的一维是非常普遍的事.

It is very common to optimize iterative DP algorithms to remove one dimension of the DP matrix along the major axis of the algorithm's progression.

例如，通常使用2D矩阵描述通常的最长公共子序列"算法，但是如果该算法从左到右进行运算，则实际上只需要2列的空间.

The usual 'longest common subsequence' algorithm, for example, is usually described with a 2D matrix, but if the algorithm progresses from left to right, then you really only need space for 2 columns.

Kadane的算法是应用于一维问题的类似优化，因此整个DP阵列都消失了.您的问题中的DP代码出于某些原因具有2D矩阵.我不知道为什么-这真的没有道理.

Kadane's algorithm is a similar optimization applied to a 1D problem, so the whole DP array disappears. The DP code in your question has a 2D matrix for some reason. I don't know why -- it doesn't really make sense.

此网站在解释推论上做得很好: https://hackernoon.com/kadanes-algorithm-explained-50316f4fd8a6

This site does a pretty good job of explaining the derivation: https://hackernoon.com/kadanes-algorithm-explained-50316f4fd8a6

这篇关于Kadane的算法是贪婪的还是优化的DP?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！