I started taking a look at a programming challenge I had read about earlier today on 8thlight. Unfortunately, it seems to have been taken down and all I could remember about it was the problem posed: Given an array of integers, find the maximum sum of contiguous values (a sub-array).
I wanted to tackle the problem from a TDD standpoint rather than diving right in, as the poster had recommended. I didn't see his solution, but what I ended up with was remarkably like Kadane's algorithm, despite having never seen or heard of it until after writing my code and attempting to make this post.
My question is as follows: Is there some extraneous logic in here that could be refactored away? Or perhaps more critically, can you provide any test cases that break this? Some solutions I've seen now that I am searching have special restrictions, such as not being able to work with arrays full of negative numbers, while mine will solve them correctly.
public static int HighestContiguousSum(int[] inputArray)
{
int currentSum = inputArray[0];
int bestSum = inputArray[0];
for (int i = 1; i < inputArray.Length; i++)
{
int value = inputArray[i];
if (bestSum < 0 && bestSum < value)
{
bestSum = value;
currentSum = value;
}
else if (value > 0 || (value < 0 && value > -1 * currentSum))
{
currentSum += value;
bestSum = Math.Max(currentSum, bestSum);
}
else if (value <= -1 * currentSum)
{
currentSum = 0;
}
}
return bestSum;
}
I ended up with ~11 tests, although not all of them are probably required (some were me just trying to break things after the fact to prove to myself it was working).
int.MaxValue
is an element and there are any positive numbers anywhere before it or immediately following it. \$\endgroup\$ – Bobson Feb 7 '13 at 15:01int.MaxValue
case entirely. I'll adjust this when I'm able. \$\endgroup\$ – jtheis Feb 7 '13 at 15:04int.MaxValue
, unless you acceptint
s but do all the math inlong
variables and return along
. Don't forget about(int.MaxValue - 1)
too - you can't just handle the one case. \$\endgroup\$ – Bobson Feb 7 '13 at 15:08