Kadane maximum subarray

Find the maximum sum of subarray with Kadane's algorithm

//test case 
int maxKanade, startKanade, endKanade;
maxKanade = Kadane(new List() { 2, -4, 6, -3, 9 }, out startKanade, out endKanade);
Debug.WriteLine("{0} {1} {2}", maxKanade, startKanade, endKanade);
maxKanade = Kadane(new List() { 3, 4, 6, -3, -9 }, out startKanade, out endKanade);
Debug.WriteLine("{0} {1} {2}", maxKanade, startKanade, endKanade);
//test case end

public static int Kadane(List input, out int start, out int end)
{
    //from wiki https://en.wikipedia.org/wiki/Maximum_subarray_problem
    //def max_subarray(A):
    //max_ending_here = max_so_far = 0
    //for x in A:
    //    max_ending_here = max(0, max_ending_here + x)
    //    max_so_far = max(max_so_far, max_ending_here)
    //return max_so_far
    start = 0;
    int s = 0;
    end = 0;
    int count = 0;
    int max_ending_here = 0, max_so_far = 0;
    foreach(int i in input)
    {
        if (max_ending_here + i > 0)
        {
            max_ending_here += i;
        }
        else
        {
            // if go negative basically take a fresh start
            max_ending_here = 0;
            s = count + 1;
        }
        if (max_so_far < max_ending_here)
        {
            max_so_far = max_ending_here;
            end = count;
            start = s;
        }
        count++;
    }
    return max_so_far;
}

Testing

When @200_success asked if you had tested the code you seemed puzzled and pointed out that you had included two tests. Unfortunately, writing things out to the screen and sight checking the results would not be considered good unit testing and for a reviewer they are not very useful as all we can tell is that some output was displayed. There is nothing to indicate what the expected results were or if they were achieved.

Also, two unit tests which pass is a limited subset to say that it is working.

What happens with an empty input?

What happens if they are all negative?

What happens if we have two sub-arrays which both have the same maximum value?

• to a degree this is a gap in the requirements, the original Kadane only cares about the max value not the start and end.

Should we return start = 0 and end = 0 if there are no elements in the input or if all are negative. The result (0) is correct but it seems to indicate an array of length starting at 0, ending at 0.

Bottom line: Testing a function like this is a great place to use an automated unit testing framework. It may seem like doubling the code to be written but by the time one has run the code, read and checked the answers and repeated umpteen times for each tweak to the code to deal with the next thing we hadn't thought of, it does save time and gives a nice warm fuzzy feeling that we can see that it works and if any changes break it.

API

We do not use the List functionality anywhere in the function but insist that the user passes in a List. I would push for changing the interface to IEnumerable.

StackExchange Code Review Q#156062, answer score: 2