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

Question

我有以下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]

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

提前致谢.

Answer 1

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

• 如果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].