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"

## No comments:

## Post a Comment