Kadane用于查找具有最大和的子arrays的算法

我有以下Kadane算法的实现来解决数组的最大子数组的问题：

public static decimal FindBestSubsequence (this IEnumerable source, out int startIndex, out int endIndex) { decimal result = decimal.MinValue; decimal sum = 0; int tempStart = 0; List tempList = new List(source); startIndex = 0; endIndex = 0; for (int index = 0; index  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]时失败。

对于我的生活，我找不到错误的位置。 也许它是算法设计的缺陷？

提前致谢。

Answer 1

您的初始实施遭受主扫描周期内不必要的复杂和部分错误的检查。 这些检查有两个：

• 如果找到更大的中间sum ，则将其作为临时结果存储;
• 独立地，如果sum负，则将其重置为0并准备从下一个扫描位置构建新序列。

重构的FindBestSubsequence方法实现如下：

 public static decimal FindBestSubsequence (this IEnumerable source, out int startIndex, out int endIndex) { decimal result = decimal.MinValue; decimal sum = 0; int tempStart = 0; List tempList = new List(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 ，上面的代码产生了正确的答案5,[1,2]而且它正确地处理了所有负数的数组而没有任何额外的代码：输入-10,-2,-3将返回-2,[1,1] 。

Answer 2

在你的例子中，即使在循环的第一次迭代中sum<0 ，你也总是得到sum > result ，因为0 > decimal.MinValue 。

所以你永远不会去你的第二个案例.-

如果添加条件sum > 0则需要更改第一个：

 if ((sum >0 ) & ((sum > result) || (sum == result && (endIndex - startIndex) < (index - tempStart)))) { ... } else if (sum < 0) { ... } 

更新：

正如我在评论中所解释的那样，您只需将结果的初始化更改为0：

 decimal result = 0; 

来自维基百科：

此子数组为空（在这种情况下，其总和为零）或由比前一个位置结束的最大子数组多一个元素组成

因此，如果数组仅包含负数，则解是一个空的子数组，其总和为0。

Answer 3

改变这一行：

 decimal result = decimal.MinValue; 

至

 decimal result = 0; 

Answer 4

对于每个位置，您应该使用其中的最大值（从原始序列）和您编写的总和。 如果原始数字较大，则最好从“开始”开始求和，即sum = max(sum+tempList[index],tempList[index]); 那么你根本不需要总和<0的情况。

Answer 5

最后，这是我纠正算法以处理所有场景的方式，以防万一它对某人有帮助：

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

Answer 6

建立在Gene Belitski的回答和评论之上：

  public static void Main() { var seq = new[] { -10M, -2M, -3M }; var stuff = seq.FindBestSubsequence(); Console.WriteLine(stuff.Item1 + " " + stuff.Item2 + " " + stuff.Item3); Console.ReadLine(); } public static Tuple FindBestSubsequence(this IEnumerable source) { var result = new Tuple(decimal.MinValue, -1L, -1L); if (source == null) { return result; } var sum = 0M; var tempStart = 0L; var index = 0L; foreach (var item in source) { sum += item; if (sum > result.Item1) { result = new Tuple(sum, tempStart, index); } if (sum < 0) { sum = 0; tempStart = index + 1; } index++; } return result; }