c++ - 最大连续子序列——动态规划还是贪心算法？

Question

给定一个数组 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] 应用不同的策略。是积极的还是消极的，一个本地可检查的条件。那为什么这个问题会出现在动态规划章节呢？

Answer 1

这是 Kadane's algorithm for the maximum subarray problem .它扫描整个序列并跟踪通常在本次迭代之前找到的最大子数组和，以及恰好在此点结束的最大子数组和。它如何知道导致最佳总和的子数组的起始位置正是这一点？每当 1) 前一个总和为负，并且 2) 遇到正元素时，从正元素开始并从那里继续是值得的。它有效的证明是通过简单的归纳法。

该算法不贪心，但可以看作是动态规划。

贪婪算法做出局部最优猜测，并坚持下去(只是越走越远)。在这里，相反，算法可以猜测检查从某个点开始的子序列(其中以正元素结尾的和为负)，然后丢弃它并尝试从其他点开始的子序列(同样，因为和变为负数)且元素为正)。

反之，它可以看作是一个动态规划问题。正如维基百科条目所说:

Because of the way this algorithm uses optimal substructures (the maximum subarray ending at each position is calculated in a simple way from a related but smaller and overlapping subproblem: the maximum subarray ending at the previous position) this algorithm can be viewed as a simple example of dynamic programming.