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

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 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  -1 * currentSum)
     currentSum += value;

and

if (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.

StackExchange Code Review Q#21405, answer score: 2