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

对于我的一生，我找不到错误在哪里。也许是算法设计的缺陷？

提前致谢。

4

6 回答 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].

于 2012-03-27T16:22:40.980 回答
3

在您的示例中，sum > result即使sum<0在循环的第一次迭代中，您也总是有，因为0 > decimal.MinValue.

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

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

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

更新：

正如我的评论中所解释的，您可以将 result 的初始化更改为 0 ：

decimal result = 0;

来自维基百科：

这个子数组要么是空的（在这种情况下它的总和为零），要么包含比在前一个位置结束的最大子数组多一个元素

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

于 2012-03-27T13:22:40.107 回答
1

更改此行：

decimal result = decimal.MinValue;

至

decimal result = 0;
于 2012-03-27T13:36:58.850 回答
0

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

于 2012-03-27T13:37:20.777 回答
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;
    }
于 2012-03-27T16:12:00.437 回答
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;
    }
于 2012-04-05T15:47:23.337 回答