# Maximum Sub-array Problem

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

-
If you want us to review the tests, you should include those too. –  svick Feb 7 '13 at 11:18
I will do so as soon as possible, I don't have them available at the moment. –  jtheis Feb 7 '13 at 15:01
In addition to the two cases @jesse-c-slicer pointed out, it also misbehaves if int.MaxValue is an element and there are any positive numbers anywhere before it or immediately following it. –  Bobson Feb 7 '13 at 15:01
@Bobson - see my comment to @jesse-c-slicer. I did strip out the vaidation code, although it seems I shouldn't have! I had the two he mentioned, and I assumed I was done. I missed the int.MaxValue case entirely. I'll adjust this when I'm able. –  jtheis Feb 7 '13 at 15:04
@jtheis - I'm not sure there's much you can do about int.MaxValue, unless you accept ints but do all the math in long variables and return a long. Don't forget about (int.MaxValue - 1) too - you can't just handle the one case. –  Bobson Feb 7 '13 at 15:08

I wanted to tackle the problem from a TDD standpoint

and

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

You should look at other options for example QuickCheck (Haskell), but there apparently is a F# port [fscheck][1]. Basic idea is the quickcheck asserts some invariant of the output value of a function.

Or in the same vein but more simply, why not test the following cases: For each array with a length between 1 and 5 and whose each element is one of {-2, -1, 0, 1, 2}. It gives you tests in 10s of thousands tests, not several; and exhaustively searches the most interesting, albeit small, portion of the problem domain. You can generate and store the answers or can generate them on the fly.

This is the black box part.

For white box part you can check the internal invariants of the algorithm. You can use Debug.Assert or whatever else your compiler gives you.

  if (bestSum < 0 && bestSum < value)
{
bestSum = value;
currentSum = value;
}

...........

bestSum = Math.Max(currentSum, bestSum);


snippets are repetitive

So is value > -1 * currentSum and value <= -1 * currentSum.

Moreover, (currentSum + value) > 0 is more readable than value > -1 * currentSum. Similarly (currentSum + value) <= 0 is more readable than value <= -1 * currentSum. Also note there is another currentSum + value hidden in currentSum += value.

Compare

if (value < 0 && value > -1 * currentSum)
currentSum += value;


and

if (value < 0 && (currentSum + value) > 0)
currentSum = currentSum + value;


currentSum is called currentSum but most of the time holds the previousSum. This isn't semantic nitpicking. Correct naming is valuable in itself, but this also prevents you from bestSum = Math.Max(currentSum, bestSum); right at the end of the for loop. Which is an important loop invariant. That is expressed succinctly in a single site. As it is, this is provided by the two bestSum= assignments mentioned above. But it requires the reader to reason (rightly or wrongly) third clause and the conspicuously missing 4th (else) clause in the conditional analysis of the code does not break the invariant (that is bestSum remains the maximal sub-array sum).

if (bestSum < 0 && means we only encountered negative numbers and this is a special case and should be handled lower than the main cases. Or better yet do not handle this case separately.

Is there some extraneous logic in here that could be refactored away?

I think your algorithm is not fundamentally different Kadane's algorithm, unless there is a missed case in the confusing conditional.

-
This is awesome and exactly what I was looking for. I will have to take a look at this and see if I can refactor away some of the cruft. –  jtheis Feb 7 '13 at 15:02

A couple of very simple tests that would fail would be to call your method with a parameter of null or new int[0]. Also, I'm not a big fan of using arrays so I did a tiny bit of rework on it to use a simple enumerable as well as guard against those edge cases.

EDIT: re-did with LINQ for the Enumerator haters :)

        if (inputSequence == null)
{
throw new ArgumentNullException("inputSequence");
}

if (!inputSequence.Any())
{
throw new ArgumentException("input should not be an empty sequence.");
}

var currentSum = inputSequence.First();
var bestSum = currentSum;

foreach (var value in inputSequence.Skip(1))
{
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;
}

-
Not sure using IEnumerator cleaned things up, as for me it just added more clutter. Cases when you need to iterate manually without foreach are quite rare... –  almaz Feb 7 '13 at 9:22
I also think that using IEnumerator directly just to verify that the input is not empty is an overkill. I think it would be simpler to use foreach together with a flag and check that flag after the foreach. –  svick Feb 7 '13 at 11:20
Accepting an IEnumerable<T> is good design. I would +1 if it were not for the clutter of accessing the enumerator directly. foreach is the way to go - in combination with LINQ .Any() if you want to guard against empty sequences. –  codesparkle Feb 7 '13 at 11:43
I think it would be interesting to explain a bit what changes you did and why you did them instead of only providing a new version. –  Quentin Pradet Feb 7 '13 at 12:40
Actually, the original did include the input validation. Those were my first tests actually. :) It also included some comments. I stripped it all down to its bare essence to hopefully focus on the logic and whether it was too verbose or repetitive, rather than precipitate a commenting style argument. –  jtheis Feb 7 '13 at 14:59

You can avoid using if statements entirely if you don't mind making assignments each iteration (untested):

public static int HighestContiguousSum(IEnumerable<int> inputSequence)
{
int bestSum = inputSequence.First();
int currentSum = Math.Max(bestSum, 0);

foreach (var value in inputSequence.Skip(1))
{
int newSum = value + currentSum;
bestSum = Math.Max(bestSum, newSum);
currentSum = Math.Max(newSum, 0);
}
return bestSum;
}


It's pretty simple if you recognize a few key properties:

1. The currentSum is always non-negative.
2. The newSum is always the current value plus the currentSum.
3. The bestSum is always the maximum of the previous bestSum and the newSum.

In general, I favor using expressions over statements (see Expressions vs. statements). It generally leads to safer, more readable code. If you want to avoid statements altogether, you could replace the foreach loop with a call to IEnumerable.Aggregate:

public static int HighestContiguousSum(IEnumerable<int> inputSequence)
{
int initialBestSum = inputSequence.First();
int currentSum = Math.Max(initialBestSum, 0);
int bestSum = inputSequence
.Skip(1)
.Aggregate(Tuple.Create(initialBestSum, currentSum), GetNext, x => x.Item1);
return bestSum;
}

private static Tuple<int, int> GetNext(Tuple<int, int> bestAndCurrentSum, int value)
{
int newSum = value + bestAndCurrentSum.Item2;
return Tuple.Create(Math.Max(bestAndCurrentSum.Item1, newSum), Math.Max(newSum, 0));
}


But as you can see, working with aggregates in C# can be clunky.

-
Also helpful. I'll be taking a look at this as well. –  jtheis Feb 8 '13 at 0:19