相关疑难解决方法(0)

Initialize:
    max_so_far = 0
    max_ending_here = 0

Loop for each element of the array
   (a) max_ending_here = max_ending_here + a[i]
   (b) if(max_ending_here < 0)
         max_ending_here = 0
   (c) if(max_so_far < max_ending_here)
          max_so_far = max_ending_here
 return max_so_far

我可以帮助我理解上述算法中最佳的子结构和重叠问题(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]并且也可以通过在第 i 个位置开始一个子阵列来单独形成A[i]并且最后我们可以在这个 DP 数组中搜索标记为 true 的最大 j！

注意：DP[i][j]表示是否可以使用以 i 结尾的子数组来生成 j！在这里我假设 j 也可以是负数。！现在可以很容易地推导出 sum+ 一个负数 < sum 。这意味着添加任何负指数无助于获得更好的总和，这就是我们可以放弃它们的原因！Morover 我们关心直到i-1th 位置的最大 j并将它与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 …