Kadane's algorithm to find subarray with the maximum sum [duplicate]

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

Answer 2

In your example you always have sum > result even if sum<0 in the first iteration of The loop because 0 > decimal.MinValue.

So you never go to your second case.-

You need to change the first if by adding a condition sum > 0:

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

Update:

As explained in my comment you can just change the initialisation of result to 0 :

decimal result = 0;

From wikipedia :

This subarray is either empty (in which case its sum is zero) or consists of one more element than the maximum subarray ending at the previous position

Therefore if the array contains only negative numbers the solution is an empty subarray with sum 0.

Answer 3

Change this line:

decimal result = decimal.MinValue;

to

decimal result = 0;