Kadane的算法找到子阵列具有最大总和

本文介绍了Kadane的算法找到子阵列具有最大总和的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我有以下的执行 Kadane算法的解决的最大子阵列的问题数组：

I have the following implementation of Kadane's algorithm to solve the problem of the maximum subarray of an array:

public static decimal FindBestSubsequence (this IEnumerable<decimal> source, out int startIndex, out int endIndex) { decimal result = decimal.MinValue; decimal sum = 0; int tempStart = 0; List<decimal> tempList = new List<decimal>(source); startIndex = 0; endIndex = 0; for (int index = 0; index < tempList.Count; index++) { sum += tempList[index]; if ((sum > result) || (sum == result && (endIndex - startIndex) < (index - tempStart))) { result = sum; startIndex = tempStart; endIndex = index; } else if (sum < 0) { sum = 0; tempStart = index + 1; } } return result; }

它失败时，我使用了负数像开头的序列 -1，2，3 给出的结果 4，[0 ，2] 而不是 5，[1,2] 。

It fails when I use a sequence that starts with a negative number like -1, 2, 3 giving a result of 4, [0,2] instead of 5, [1,2].

有关我的，我找不到在哪里的错误是企业的生命。也许它的算法设计缺陷？

For the life of me that I cannot find where the error is. Maybe its a defect on the algorithm design?

在此先感谢。

推荐答案

您最初的实现不必要地复杂，部分错误检查所受内的主扫描周期。这些检查有两种：

Your initial implementation suffered from unnecessarily complicated and partially wrong checks within the main scan cycle. These checks are two:

• 如果较大的中间之被发现，将其存储成分作为临时结果;
• 独立，如果之有负，其重置为 0 和prepare建立一个新的序列从明年扫描位置。

• if greater intermediate sum is found, store it constituents as a temporary result;
• independently, if sum got negative, reset it to 0 and prepare to build a new sequence from next scan position.

重构的 FindBestSubsequence 方法的实现如下所示：

Refactored FindBestSubsequence method implementation is listed below:

public static decimal FindBestSubsequence (this IEnumerable<decimal> source, out int startIndex, out int endIndex) { decimal result = decimal.MinValue; decimal sum = 0; int tempStart = 0; List<decimal> tempList = new List<decimal>(source); startIndex = 0; endIndex = 0; for (int index = 0; index < tempList.Count; index++) { sum += tempList[index]; if (sum > result) { result = sum; startIndex = tempStart; endIndex = index; } if (sum < 0) { sum = 0; tempStart = index + 1; } } return result; }

现在不仅对 1,2,3- 的code以上产生正确答案 5，[1,2] 而且它正确处理所有负数阵列无需任何额外的code：进入 -10，-2，-3 返回 -2，[1,1] 。

Now not only for -1,2,3 the code above produces correct answer 5,[1,2] but also it correctly processes arrays of all negative numbers without any extra code: entering -10,-2,-3 will return -2,[1,1].