The most common non-periodic hang is a Sweep Hang.
Here DP sweeps across the data, going back and forth.
It will extend the sequence at one or both ends while doing so.
This causes the sequence to grow, which means that it takes increasingly more time to traverse the sequence, which is why the hang is not periodic.
Sweep Hangs require two loops.
One loop moves DP to the right, until it encounters the end of the sequence.
It then switches to the other loop, which moves DP leftwards.
Figure 1 shows a typical example.
Sweep hangs have several variation points.
First, does the sequence extend both ways?
- Dual Headed.
The sequence extends both ways.
The hang in Figure 1 is an example.
- Single Headed.
The sequence extends only one way.
The hang in Figure 2 is an example.
When the sequence is Dual Headed, do both ends grow at the same pace?
- Balanced Growth.
The sequence grows at the same pace at both ends.
The hang in Figure 1 is an example.
- Unbalanced Growth.
One side of the sequence grows more slowly than the other.
The hang in Figure 3 is an example.
When the sequence is Single Headed, does DP traverse the entire sequence?
- Full Sweep.
DP traverses the entire sequence.
The hang in Figure 3 is an example.
- Partial Sweep.
DP traverses only a subset of the non-zero values;
it changes direction mid-sequence.
The hang in Figure 4 is an example.
In this case, there's only a single non-zero disconnected value, but there can be more.
Two types of Partial Sweep hangs exist:
- Zero Bounded.
The mid-sequence turning point is zero.
The hang in Figure 4 is an example.
- Non-Zero Bounded.
The mid-sequence value where DP changes direction is only briefly zero when it is visited.
The hang in Figure 5 is an example.