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.