给定一个带有正负条目的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]是有效的还是阴性的(可本地检查的条件)应用不同的策略。那么,为什么这个问题出现在动态编程章节中?

最佳答案

这是Kadane's algorithm for the maximum subarray problem。它扫描整个序列并跟踪直到此迭代为止找到的最大子数组总和,并且最大子数组总和恰好在此点结束。如何知道子数组的起始位置,直到此时才达到最佳汇总?每当1)前一个和为负数,和2)遇到正数元素时,从正数元素开始并从那里继续是值得的。通过简单的归纳即可证明其有效。

该算法不是贪婪的,但是可以看作是动态编程。

贪心算法会做出局部最优猜测,并且坚持下去(只是不断地进行下去)。相反,在这里,算法可以猜测检查从某个点开始的子序列(其中以正元素结尾的和为负),然后丢弃它并尝试从其他点开始的子序列(再次,因为和为负。且元素为正)。

相反,可以将其视为动态编程问题。正如Wikipedia条目所述:

10-05 20:43
查看更多