Thursday, May 5, 2011

Fascinating problems for the maximum subsequence problems

The linear solution for the maximum contiguous subsequence problem is one of most fascinating solution for a problem that is cubic at first glance. Sometime this problem is also known as Maximum subarray problem, and the idea is that you have an array of positive and negative integers and you need to find a "slice" whose sum is maximum (e.g.−2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6). The linear solution is one the pearls in Bentley's book

maxsofar = 0
maxendinghere = 0
for i = [0, n)
/* invariant: maxendinghere and maxsofar are accurate
are accurate for x[0..i-1] */
maxendinghere = max(maxendinghere + x[i], 0)
maxsofar = max(maxsofar, maxendinghere)

The key observation is to maintain the maximum found so far, putting a zero as minimum because that's the empty sequence. Then we have another variable for computing the global maximum among all the local maximum.

Now given this pearl, can you solve the following problem: "Given an array of 0s and 1s, Find the maximum contiguous subsequence so the number of 0's and 1's in that subsequence are equal"