Kadane maximum subarray

Question

Find the maximum sum of subarray with Kadane's algorithm

//test case 
int maxKanade, startKanade, endKanade;
maxKanade = Kadane(new List<int>() { 2, -4, 6, -3, 9 }, out startKanade, out endKanade);
Debug.WriteLine("{0} {1} {2}", maxKanade, startKanade, endKanade);
maxKanade = Kadane(new List<int>() { 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<int> 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;
}

• 200_success: Have you tested this code?
• paparazzo: @200_success What? I included 2 test cases?
• 200_success: And where is Kanade() defined?
• paparazzo: @200_success Sorry I had a misspell I semi fixed after the copy. I will fix.
• greybeard: Sorry I had a misspell - had? int maxKanade, startKanade, endKanade; and uses thereof. (Then, misspell is no noun in my book.)

Answer 1

You could simplify that

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

with

max_ending_here += i;
if (max_ending_here <= 0)
{
 // if go negative basically take a fresh start
 max_ending_here = 0;
 s = count + 1;
}

• paparazzo: I ended up with something different but this got me going in that direction.

Answer 2

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

• AlanT: It's a variation on an established algorithm - the original is a lot simpler because it doesn't care about start or end positions. The point of the comment is that sight checking Debug.WriteLine() statements as a mechanism for testing doesn't scale well.

Answer 3

A small contribution. This code block looks a bit unpleasant:

start = 0;
int s = 0;
end = 0;
int count = 0;
int max_ending_here = 0, max_so_far = 0;

You have two declaration styles, I would say that mixing them up isn't "fashionable" -- I guess is the word?

You could go with something like:

start = 0;
end = 0;
int s, count, max_ending_here, max_so_far = 0;

or

start = 0;
end = 0;
int s = 0;
int count = 0;
int max_ending_here = 0;
int max_so_far = 0;

Answer 4

Can move the check on max_so_far to inside the max_ending_here += i;
No reason to process 0

foreach(int i in input)
{
 if (i == 0)
 { }
 else if (max_ending_here + i > 0)
 {
 max_ending_here += i;
 if (max_so_far < max_ending_here)
 {
 max_so_far = max_ending_here;
 end = count;
 start = s;
 }
 }
 else
 {
 // if go negative basically take a fresh start
 max_ending_here = 0;
 s = count + 1;
 } 
 count++;
}