Kadane's algorithm to find subarray with the maximum sum

Question

I have the following implementation of Kadane's algorithm to solve the problem of the maximum subarray of an array:

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

It fails when I use a sequence that starts with a negative number like -1, 2, 3 giving a result of 4, [0,2] instead of 5, [1,2].

For the life of me that I cannot find where the error is. Maybe its a defect on the algorithm design?

Thanks in advance.

Answer 1

Your initial implementation suffered from unnecessarily complicated and partially wrong checks within the main scan cycle. These checks are two:

• if greater intermediate sum is found, store it constituents as a temporary result;
• independently, if sum got negative, reset it to 0 and prepare to build a new sequence from next scan position.

Refactored FindBestSubsequence method implementation is listed below:

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

Now not only for -1,2,3 the code above produces correct answer 5,[1,2] but also it correctly processes arrays of all negative numbers without any extra code: entering -10,-2,-3 will return -2,[1,1].