logo标签列表

Kadane算法：寻找具有最大和的子数组

c#.netalgorithmkadanes-algorithm
8

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

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]。

我真的找不到错误在哪里。也许这是算法设计上的缺陷？

提前感谢。

6个回答
8

您的最初实现在主要扫描周期内进行了不必要的复杂和部分错误的检查。这些检查有两个：

  • 如果发现更大的中间sum，则将其构成部分存储为临时结果；
  • 独立于此，如果sum变为负数，则将其重置为0并准备从下一个扫描位置开始构建新序列。

重构后的FindBestSubsequence方法实现如下：

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，上述代码会生成正确的答案5,[1,2]，而且它可以正确地处理所有负数数组，无需编写任何额外的代码：输入-10,-2,-3将返回-2,[1,1]。

1
太好了。我刚刚拿了一个看起来很标准的C语言实现，然后将其移植到了C#中。你的代码通过了我所有的单元测试，所以我认为这是最好的选择。谢谢！ - Ignacio Soler Garcia
1
此外，如果你正在重构代码，我建议直接遍历IEnumerable，不需要创建列表的副本。同时传递多个“out”参数通常是不好的实践，最好使用自定义返回类型。 - vgru
2
同意列表副本。不同意创建新的返回类型，因为在这种情况下开始索引和结束索引的使用似乎非常明显。 - Ignacio Soler Garcia
3
在您的示例中，即使在循环的第一次迭代中sum<0，您始终具有sum > result，因为0 > decimal.MinValue。

因此，您永远不会进入第二种情况。

您需要更改第一个if语句，通过添加条件sum > 0来实现：

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

更新：

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

decimal result = 0;

来自维基百科:

这个子数组要么为空（此时其总和为零），要么比前一个位置结束的最大子数组多一个元素

因此，如果数组只包含负数，则解决方案是一个总和为0的空子数组。

如果我进行这个更改，那么算法会在所有值为负的序列中失败。 - Ignacio Soler Garcia
1
你可以为这种情况添加一个case，返回一个空列表和0，或者如果你不想返回0，就返回列表中的最大值。 - Ricky Bobby
我同意，但这是否意味着Kadane算法有缺陷？ - Ignacio Soler Garcia
不，我认为将结果初始化为0会给你与在第一个if条件语句上添加条件相同的输出（我的答案），而且它也能正常工作。 - Ricky Bobby
我找到的算法实现中都没有包括这些条件（Kadane的伪代码也没有）。 - Ignacio Soler Garcia
1
@SoMoS：是的，Ricky说得对，未经修改的Kadane算法对于负数来说根本不适用，因为它每次都从零开始。 - vgru
1

更改此行：

decimal result = decimal.MinValue;

到

decimal result = 0;
当所有值都为负数时，"Thanks" 使算法返回0。对于输入的-1、-2、-3，最佳子数组是-1。 - Ignacio Soler Garcia
@SoMoS：没错，我刚刚比较了你的代码和你发布的维基百科文章。这也意味着他们的Python示例也存在同样的问题。 - vgru
1
Kadane算法由扫描数组值组成，在每个位置计算以该位置结尾的最大子数组。这个子数组要么为空（在这种情况下其总和为零），要么比前一个位置结束的最大子数组多一个元素。 - Ricky Bobby
0

最终，这就是我如何纠正算法以处理所有情况的方法，以防对某人有所帮助：

    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);

        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;
    }
感谢Ricky Bobby和Groot指引我正确的方向。 - Ignacio Soler Garcia
以上代码仍然可以进行一些重要的改进，例如删除不必要的特殊情况处理和所有负数数组。您可以查看我重新编写的“FindBestSequence”实现。 - Gene Belitski
0

基于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<decimal, long, long> FindBestSubsequence(this IEnumerable<decimal> source)
    {
        var result = new Tuple<decimal, long, long>(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<decimal, long, long>(sum, tempStart, index);
            }

            if (sum < 0)
            {
                sum = 0;
                tempStart = index + 1;
            }

            index++;
        }

        return result;
    }
0
对于每个位置，您应该取该位置的值（来自原始序列）和您编写的总和中的最大值。如果原始数字更大，则最好从“开始求和”开始，即sum = max(sum+tempList[index],tempList[index]); 然后您根本不需要考虑 sum < 0 的情况。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接