****** A quick note by Kun-Mao Chao (Oct. 18) ******

Assume the following scoring scheme:
    A match is given a bonus +8;
    A mismatch is penalized by -5;
    A gap of length between 1 and 20 is given a constant penalty -20;
    A gap of length between 21 and 100 is given a constant penalty -30;
    A gap of length more than 100 is given a constant penalty -40;

To determine the best alignment ending with a gap of length
between 21 and 100, we need to find the maximum among
S(i, j-100), S(i, j-99), ..., S(i, j-21).

Basically, we need to be able to answer efficiently the maximum
value in a shifting window whose size is fixed. By maintaining
a linked list of decreasing scores, each window's maximum can
be answered efficiently. For example, suppose we are given the following
sequence, and window size 5:

    2  7  3  6  1  4  0   9   5   8

The first window is 2  7  3  6  1, whose maximum is 7.
When we move to the next window 7  3  6  1  4,
its maximum is still 7.
Then 3  6  1  4  0, its maximum is 6.
Then 6  1  4  0  9, its maximum is 9.
Then 1  4  0  9  5, its maximum is 9.
Then 4  0  9  5  8, its maximum is 9.

What we do is to maintain a list of candidates in decreasing order.
Initially, the list is 7  6  1. (We can see that 3 won't be able to
stand out because 6 will always be a better choice later.)
When we add 4, we scan the list from the back and kill
all those items less than or equal to 4, resulting the list 7  6  4.
The first item of the list is the maximum of the current window.
Then the list becomes 6  4  0. The maximum is 6.
Then the list becomes 9. The maximum is 9.
...

Time: Though we might have to do more than O(1) operations for some single
housekeeping sweeps, these costs could be amatized to each entry in the linked list
since the entry is added to the list once, and when it is removed from the list, it's gone forever. Thus, in total the running time is O(n) for a sequence of size n.