Our first intuition when looking at an algorithmic problem is to think of the whole input and try to find a solution for it. We carry with us the intuition of the physical world; when we try to solve a problem, we have to deal with all of it. The incremental method is different. It assumes that you have already found a solution, and now someone gives you a slightly larger problem and asks you to extend the solution. If you can find a general way to extend the solution, then you can start with an empty input and keep extending it. Concentrating on the incremental is often easier and it leads to powerful techniques for attacking problems.
I called this method the "induction method" in my book Introduction to Algorithms: A Creative Approach (Addison-Wesley, 1989), because it employs the same principle as mathematical induction. Since then, I found that induction intimidates many people, and using it in this context can confuse things. So I'll stick with "incremental method" here, which is a clearer and more descriptive name.
The maximum rectangle problem, described wonderfully by David Vandevoorde in his article "The Maximal Rectangle Problem" (DDJ, April 1998), turns out to be a perfect example to illustrate the incremental method. (Vandevoorde referred to the problem as the "maximal rectangle problem," but "maximum" problem is more precise, because maximal usually means something that cannot be extended, whereas maximum means the global maximum.) The incremental method is not perfect, and it is not always the best way, but it is applicable most of the time, and it is definitely a technique every algorithm designer should keep in their arsenal.
The maximum rectangle problem can be summed up as:
The input: An N×M binary matrix B.
The output: A rectangle in B of maximum area containing all 1s.
The first issue when trying the incremental method is to define the incremental. For matrices, there aren't too many choices; either you add a new row or a new column. (I'll show later that this is not always straightforward.) Let's try a new row. Assume that you have found the largest rectangle in the original matrix, and that you are now given one additional row. You need to determine if there is an even larger rectangle with the new row. That already limits your search. You need to consider only rectangles that end at the last row. So all the 0s in the last row do not contribute. That means that you can divide the problem into several subproblems by looking only at intervals in the last row that contain only 1s; see Figure 1. The subproblems are independent of one another, so you need to consider only one of them at a time. The same solution will apply to all of them.
Looking at each subproblem, you are now looking for the maximum rectangle that ends at the last row, and you know that the last row contains all 1s. So you need to know, for each column i, the length of the bottom block of 1s; call it Ci. This kind of information is easy to maintain as you add rows; for each column, you either increment the bottom block length (if the last row contains a 1) or set it to 0 (if it contains a 0). The division into subproblems is used here mostly for simplicity; you can just as easily consider the whole row, with the 0s, as one problem. Given this information, you can now define your problem as a one-dimensional problem:
The input: a sequence of integers, C1, C2, ..., Ck.
The output: the interval [i,j] that maximizes the product of the length of the interval (j-i) times the minimum number in it.
(The area of a rectangle of all 1s corresponds to such a product; the width of the rectangle corresponds to the length of the interval and its height corresponds to the minimum number in it.)
The incremental method lets you reduce a two-dimensional problem to a one-dimensional one. If you want to obtain an optimal O(MN) solution for the original problem, you will need to solve this one-dimensional problem in linear time O(k). Using the incremental method again, you assume that you know how to solve the problem up to k numbers, and you now need to handle the k+1 number; call it Ck+1. If successful, this will reduce the problem one more time and allow us to concentrate on just one number.
You need to concentrate only on intervals that end at Ck, and check how Ck+1 can change them to produce better intervals. If Ck+1>=Ck, then the best interval that ends at Ck can be extended to end at Ck+1, without changing its minimum number, so it is the best possible interval. But, as Figure 2 shows, if Ck+1<Ck, then you cannot easily determine the best interval. Without Ck+1=3, the best interval (2a) consists of the last two numbers, giving the product min{6,5}×2=10. Extending that interval to include the 3 (2b) gives min{6,5,3}×3=9, which is not better. But since the minimum number is now 3, you can use a bigger interval (2c), leading to a product of min{3,6,5,3}×4=12. If you extend it all the way (2d), you get a product of min{4,2,3,6,5,3}×6=12. There is no easy way to figure it out by looking at only Ck+1 and the best interval up to Ck. That seems like a failure of the incremental method, because concentrating on Ck+1 alone does not seem to be sufficient.
But the incremental method can be applied in many different ways, which is why it is so powerful. Incrementing by adding one number at a time to the end of the sequence is the natural thing to do, but it is not the only way to increment. Maybe instead of incrementing by looking at the last number, Ck+1, you should look at the first number, C1? In this case, the first number has the exact same effect as the last number, so this will not help. But what about the minimum number in the sequence, or the maximum number? As it turns out, using the minimum number and using the maximum number lead to two different algorithms, both optimal.
Start with the minimum number; call it m. For simplicity, I'll use m both to point to the number and to its value. How can m be involved in the solution? If the best interval contains m, then that interval might as well contain everything. In other words, if m is involved then the best interval is the whole sequence. Keep that in mind, and check the alternatives. If m is not contained in the best interval, then the best interval is somewhere to the side of m, either to the left or to the right. You have now partitioned the problem into two independent subproblems, each of which can be solved recursively, so the problem is solved. In Figure 3, you see the intervals corresponding to choosing, from top to bottom, 2, 3, 4, 5, and 6. Getting a linear-time implementation of this solution is not straightforward, but since you spent only a constant time handling m, there is hope.
Let's try the incremental method concentrating on the maximum number; call it M. This turns out to be slightly more tricky, but it leads to an easier to implement algorithm. Again, how can M be involved in the solution? There are two possibilities when M is part of the interval. Either the interval consists of M by itself, in which case its area is M×1 = M, or the interval includes one of M's neighbors as well. In the latter case, M will contribute no more than its neighbor contributes. So if you can figure out which neighbor to choose, you can assign M's contribution to that neighbor by specifying that the neighbor is worth twice its size, and do away with M. If you can do that safely, you have an incremental solution, because you can continue to handle maximum numbers one at a time.
You allocate a counter to each number to indicate how many of its neighbors should be counted when this number is used for the best interval. You then remove M and increment the counter of one of its neighbors (the mystery of which neighbor to choose will be revealed in a minute). In effect, what will happen is that when the minimum number in an interval is considered, all its larger neighbors will have been considered by then, and their number will be assigned. So at that point the smallest number will know the size of its interval.
Suppose that the numbers are in decreasing order with the largest on the left. The algorithm will take C1 as the first rectangle by itself, then increment the counter of C2 to 2. In the second step, C2 counts twice (since its counter is 2), and so its rectangle is worth 2×C2. Check whether this is larger than the previous best rectangle (C1), and take the maximum of them. You then assign C2's counter to C3 which will be set at 3, and contribute 3×C3 and so on. This is the simplest case, and in general the algorithm works just as well.
Which neighbor to use -- the smaller or the larger? The answer is the larger, because it is the safer choice. Any interval that contains one of M's neighbors will at least contain M and the larger of the neighbors (it may contain both neighbors). So by assigning M's contribution to the larger neighbor you ensure that M will be considered for any interval that contains it. An example of using this algorithm for the matrix in Figure 1 is in Figure 4. The contribution 6 is 1×6. The second largest is 5, whose counter is now 2, so it contributes 2×5. Next is 4, which assigns its contributions to its neighbor 2. Next is 3 (I chose the 3 to the right, but you could just as well chose the other one), which contributes 3×3. When the other 3 is considered, its counter is 4, so it contributes 4×3=12. The last one is 2, whose counter is now 6, leading to another best solution of 12.
The two algorithms suggested by the incremental method are not complete. You need to carefully design the right data structures to handle all the operations efficiently. The devil is in the details. But the details are easier once you have an overview and an understanding of the algorithm, which you now do. One of the strengths of the incremental method is the ease in which one gets to an algorithmic idea.
The algorithm demonstrated in Figure 4 consists of the following four steps, which are repeated for each number:
1. Find the next maximum M.
2. Check M's current contribution against the previous best.
3. Assign M's counter to its larger neighbor.
4. Delete M.
To get a repeated list of maximums you need to sort the numbers. Fortunately, all the numbers are in the range of 1 to N (since they sum the number of 1s in a column), so you can sort all of them in linear time using a simple bucket sort. Finding the neighbors of each number can be achieved by linking all the numbers in a doubly linked list, which also lets you delete each number. All these operations can be done in linear time. (The algorithm can be further simplified by noticing that the sort is not crucial, because the main step of assigning worth can be performed any time a number is larger than both its neighbors.)
The incremental method is particularly useful as a way to arrive at possible new algorithms. It can lead the way and suggest different approaches. It is not a magic bullet, and it will not replace intuition and experience, but it helps to develop both.
DDJ