Talk:Greatest subsequential sum

Currently this contains some ruby code, and no clear description of exactly what the task is. Please clarify the exact goal so others can provide implementations for the languages they use. --- crc 2007-06-21

I think the task is to find the subsequence in the array which has the largest sum of elements, or an empty sequence if all numbers are negative (is arr[0..nil] a representation of the empty sequence in Ruby?). If I understand the code correctly, it never includes leading or trailing zeroes (e.g. for the array [0, 1, 5, 3, 0] it returns [1, 5, 3]), but otherwise if there are several subsequences with the same maximal sum, the result is the first one (i.e. it doesn't generally search the shortest one; e.g. for [1, 2, 3, -100, 1, 5] it gives [1, 2, 3], not [1, 5]). However, I don't know Ruby, so I'm not completely sure I'm interpreting it correctly. Also, it's not clear to me how much of that behaviour is part of the task, and how much just happens to be a property of the specific implementation (e.g. would code which includes leading or trailing zeroes in the sequence or code which finds e.g. the last or the shortest sequence with maximal sum also solve the task?) --Ce 03:46, 24 June 2007 (EDT)

Ok, I now have changed the text to my interpretation (I've taken the most liberal interpretation, i.e. not fixing at all which subsequence to take in case more than one has the same value; I also allow empty sequences, which have sum 0, because I think that's what the Ruby code does). I've also added a C++ implementation (which I believe behaves exactly like the ruby one, thus I hope that even if my interpretation of the task turns out not to be what was meant, the code should still be correct for the task to be solved).

subarray is a somewhat unclear term

The task does not specify anything about the presumed topology of the "subarray": In some languages, the "shape" of an array can be a rather fuzzy notion, and even if your language has precise rectangular, evenly-spaced arrays, it is not clear from the spec whether the supposed "subarray" has to have a rectangular shape. For example in 2 dimensions, an array could be a grid and this task might be asking for a L-shaped area in that grid. Or maybe only convex shapes are allowed. Or, indeed, only rectangles. What if an "L" can be turned into a rectangle by adding an element that contains zero? I think there needs a much clearer statement of purpose here somewhere... Sgeier 18:13, 3 August 2007 (EDT)

From the original Ruby example code, I'd expect it to be restricted to one-dimensional arrays. That's also what I implemented in C++ (actually, my function works not only on arrays, but on any sequence accessible through forward iterators, but sequences are one-dimensional by definition, too). An obvious restriction is, of course, that the array has a finite number of elements (some languages may be able to describe infinite arrays).

Possibly renaming the article from "Maximum subarray" to "Maximum subsequence" would be a good idea (after all, the interesting part here is the algorithm, not the actual data structure used to store it; e.g. in Lisp, one might prefer to use lists rather than arrays). Or even better, rename it to something like "Subsequence with maximal element sum" (surely a better new title can be found along this line). --Ce 20:45, 4 August 2007 (EDT)