给定一个数组 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) 遇到正元素时，从正元素开始并从那里继续是值得的。通过简单的归纳即可证明其有效。
该算法不是贪婪的，但可以看作是动态规划。
贪心算法会做出局部最优的猜测，并坚持下去(只是不断地继续下去)。相反，在这里，算法可以猜测检查从某个点开始的子序列(其中以正元素结束的总和为负)，然后丢弃它并尝试从其他点开始的子序列(同样，因为总和变为负数)并且元素为正)。
相反，它可以被视为动态规划问题。正如维基百科条目所说:
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.
关于c++ - 最大连续子序列——动态规划还是贪心算法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/39733265/