Maximum Sub-array Problem

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

I think it can compress a lot more

public static int HighestContiguousSum(int[] inputArray)
{
    int currentSum = 0;
    int bestSum = 0;
    foreach (int i in inputArray.Length)
    {
        currentSum = Math.Max(0, currentSum + i);
        bestSum = MathMax(bestSum, currentSum);
    }
    return bestSum;
}