Алгоритм Кадане для поиска подмассива с максимальной суммой [дубликат]

На этот вопрос уже есть ответы здесь:

Подсписок максимальной суммы?(13 ответов)

Закрыто 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);

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

Ради жизни я не могу найти, где ошибка. Может быть, это дефект алгоритма?

Заранее спасибо.

.net algorithm c# kadanes-algorithm

задан default locale 12 April 2012 в 04:35

0 ответов

Другие вопросы по тегам:

.net algorithm c# kadanes-algorithm

Алгоритм Кадане для поиска подмассива с максимальной суммой [дубликат]

0 ответов

Похожие вопросы: