Albert Y. C. Lai trebla at vex.net
Thu Jul 19 15:44:13 EDT 2007

```Anthony Clayden wrote:
> (Or at least the problem is under-specified.)
>
> 1. There may be several sub-sequences having the maximum
> sum.
>    So the type for the solution should be :: Num a => [a] ->
> [[a]]

> 2. The inits . tails approach adds a fault:
>    It introduces a sprinkling of empty sub-sequences. These
> have sum zero.
>    So in case the input list is all negative numbers ...
>
> Being a software tester for my day job, I looked first not
> for an elegant and/or efficient solution; but for where to
> stretch the boundaries of the problem.

I am an academic into formal methods. Contrary to common myth, my
perspective is compatible with, not contrary to, the tester perspective.
If you start from testing and let one of your "size" or "coverage"
parameters tend to infinity, you arrive at a formal method. Both
perspectives demand well-scoped specifications, otherwise there is
little to test for or verify against. Thus, I also look first for
boundaries of problems.

Here are two test cases:

(A) [2, -10, 2]

(B) [-10, -11]

Following point #1, the answer to (A) may be [[2]] or [[2], [2]],
depending on whether you consider the first [2] to be "the same as" the
second [2]. Some people say, "[2]==[2], they are the same". Some other
people say, "they occur at different places, they are different, in fact
it is probably more interesting to give indexes rather than list
contents, e.g., [(0,0), (2,2)]".

If you decide they are the same, then I have little to say about (B) and
point #2, except that you should beware that the answer to (B) is [[]],
and in your effort of killing off empty lists you should be careful in
preserving one of them.

If you decide they are different, then point #2 is ill advice. As you
would consider multiple occurrences of [2] to be distinct because they
come from different positions, so you would consider multiple occurences
of [] to be distinct because they come from different positions. In (B),
there are three occurrences of []: before -10, between -10 and -11, and
after -11. All three should be reported as answers. The answer should be
[[], [], []] or [(0,-1), (1,0), (2,1)]. It is in fact paramount to use
inits . tails or equivalent to sprinkle empty subsequences, since that's
the only way you won't miss them.
```