At first glance this puzzle seems trivial, all you have to do is find a sub-array, in an array of numbers,  that sums to the largest value. It sounds almost too easy to need a solution, let alone an algorithm. But try it and see if you can write a fast and beautiful solution. It is harder than you think.

This is another puzzle featuring Joe Celko's characterful pair, Melvin Frammis, an experienced developer at International Storm Door & Software, and his junior programmer sidekick, Bugsy Cottman. The aim, as before, is to write beautiful code in the programming language of your choice.

It was a quiet day at International Storm Door & Software and Melvin Frammis was getting a Slurm Cola when junior programmer Bugsy Cottman tapped him on the shoulder.

“Got a minute?” said Bugsy. “I got assigned a quick report and it is taking forever to run. “

“Actually, I have a meeting after lunch, and ..” said Melvin.

With his usual complete obliviousness, Bugsy continued,

“We have a file of time slots and how many widgets, storm doors or somethings we added or lost in each slot. I did not pay much attention to what they were saying. They want to know which contiguous set of slots has the highest total.”

Chugging his drink, Melvin realized that he was cornered.

"I will not write your code for you, but I can get you started.” said Melvin.

Let's make this more abstract.

Use a one-dimensional array, slots[1:n], and we want to find a sub-array, slots [a:b] , where (1 <= a <= b <= n) and SUM (slots [a:b]) is a maximum.

If all the slots are positive or zero, then the sum of whole array is the answer.

Problem solved!

"Now let me get to my meeting.”

”No, no, even I thought of that.” whined Bugsy. "Some of these slots are negative values.”

He ran over to a whiteboard and wrote a quick diagram:

“ The total for all five slots is -1, so that does not work. Here is a table for all the sub-arrays.”

“See? The best sub-arrays are slots[1:2] and slots [4:5] , so a simple total summation will not work.”

“Why not use brute force? Just use two for-loops to do all the sums and keep the highest one as you compute them”, said Melvin. Putting down his drink he scratched out some pseudo-code.

BEGIN
  best_sum := 0;
  FOR a := 1 TO n
   DO FOR b := 1 TO n
    DO BEGIN
      local_sum := 0;
      FOR i := a TO b
       DO local_sum := local_sum + Slots[i];
      best_sum :=
           GREATEST (local_sum, best_sum);
    END;
END;

Bugsy replied, “Yep, for 1000 slots, there are about half a million pairs. And my data set is bigger than that. It will take forever!”

“Not forever. For (n) slots, you get (n *(n-1))/ 2 pairs and that can be a lot of pairs for a big data set. And I am using three nested loops.” said Melvin.

“But even if you have the hardware to make the brute force method workable, you have other problems. Different languages have different loops, so this might not translate well. I am depending on the 'FOR i := a TO b' to become a no-op when (b > a) in my pseudo- code. That might not be how your programming language works.

And there is another flaw. If you think about it, you can improve this algorithm quite a bit with a little work.”

Bugsy walked over to the whiteboard, stared and said, “Oh, it does not work if all the slots are negative!

But how can I make this run better?”

Melvin had escaped to his meeting when Bugsy went to the board.

Now, dear reader, your assignments are:

1. Improve this looping algorithm from O(n³) to O(n²)

2. Find different, better algorithms that work better than O(n²).