最大连续子序列 - 动态编程或贪婪算法？

给定带有正和负入场的数组vector<int> arr，最大连续子序列问题需要找到具有最大和的数组arr的（连续）片段。空段的和为零。我正在使用的算法的C++代码如下：最大连续子序列 - 动态编程或贪婪算法？

int MaxContSum(const vector<int>& arr){ 
    int i,sum=0,max=0; 
    for(i=0;i<arr.size();i++){ 
     if(arr[i]>=0) {if(sum<0) sum=0;} 
     else {if(sum>max) max=sum;} 
     sum+=arr[i]; 
    } 
    if(sum>max) max=sum; return max; 
    }

该算法是贪婪算法还是动态编程？看起来它只是逐个扫描条目，并根据arr[i]是否为负数或是否为局部可检查条件应用不同的策略。为什么这个问题出现在动态编程章节中呢？这个问题应该有才能有资格与DP解决

来源

2016-09-27 Zhuoran He

这是Kadane's algorithm for the maximum subarray problem。它扫描整个序列并跟踪一般情况下达到该迭代的最大子阵列总数，最大子阵列总和恰好在此点处结束。它是如何知道该子阵列的起始位置导致最好的总结到这一点？无论何时1）前一个总和为负数，并且2）遇到正数元素时，从正数元素开始并从那里继续是有利的。它的工作证明是通过简单的归纳。

该算法不贪婪，但它可以被视为动态编程。

一个贪婪的算法使局部最佳的猜测，并坚持下去（只是继续下去）。在这里，相反地，算法可以猜测检查从某点开始的子序列（其中结束于正元素的和为负的子序列），并且随后丢弃它并尝试从其他点开始的子序列（再次，因为和为负元素是正数）。

相反，它可以被看作是一个动态编程问题。由于维基百科条目所说的那样：

的因为这种算法采用最优子的方式（在每个位置结束的最大子阵列以简单的方式计算出从相关但更小的和重叠的子问题：在结束最大子阵以前的位置），这个算法可以被看作是一个动态编程的简单例子。

来源

2016-09-27 20:51:36

我明白了。条件'sum <0'不是本地可检查的，因为变量'sum'将过去的信息传送到当前状态。这个问题显示了研究历史的优势 - 将贪婪的决策策略转变为动态规划。我们以前的人为我们做了一个“小问题”。我们可以根据他们无法获得的信息选择是继承还是丢弃遗产。 –

'max'记录终止段的结果，'sum'记录不终止段的结果。这两种可能性都发挥出来了，当“if（sum <0）sum = 0;'step”中清楚地看到两种收益时，就做出决定。贪婪算法会做出早期决定并坚持下去。 –

两个主要特性是：

从你介绍一下，第一个属性肯定是失踪因此我不会将此算法归类为DP。另一方面，为了得到最终结果，你使用计算结果得到最终结果 - 所以我们有最佳子结构，这可能是你在动态规划章节中找到这种算法的原因，尽管它不应该属于那里。

来源

2016-09-27 20:20:13

最大连续子序列 - 动态编程或贪婪算法？

回答

相关问题