Greatest subsequential sum

From Rosetta Code

Given a sequence of integers, find a continuous subsequence which maximizes the sum of its elements, that is, the elements of no other single subsequence add up to a value larger than this one. An empty subsequence is considered to have the sum 0; thus if all elements are negative, the result must be the empty sequence.

[edit] Ada

with Ada.Text_Io; use Ada.Text_Io;
 
procedure Max_Subarray is
   type Int_Array is array (Positive range <>) of Integer;
   Empty_Error : Exception;
   function Max(Item : Int_Array) return Int_Array is
      Start : Positive;
      Finis : Positive;
      Max_Sum : Integer := Integer'First;
      Sum : Integer;
   begin
      if Item'Length = 0 then
         raise Empty_Error;
      end if;
 
      for I in Item'range loop
         Sum := 0;
         for J in I..Item'Last loop
            Sum := Sum + Item(J);
            if Sum > Max_Sum then
               Max_Sum := Sum;
               Start := I;
               Finis := J;
            end if;
         end loop;
      end loop;
      return Item(Start..Finis);
   end Max;
   A : Int_Array := (-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1);
   B : Int_Array := Max(A);
begin
   for I in B'range loop
      Put_Line(Integer'Image(B(I)));
   end loop;
exception
   when Empty_Error =>
      Put_Line("Array being analyzed has no elements.");
end Max_Subarray;

[edit] ALGOL 68

Translation of: C

Works with: ALGOL 68 version Revision 1 - no extensions to language used

Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny

Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d

main:
(
        []INT a = (-1 , -2 , 3 , 5 , 6 , -2 , -1 , 4 , -4 , 2 , -1);
 
        INT begin max, end max, max sum, sum;
 
        sum := 0;
        begin max := 0;
        end max := -1;
        max sum := 0;
 
 
        FOR begin FROM LWB a TO UPB a DO
                sum := 0;
                FOR end FROM begin TO UPB a DO
                        sum +:= a[end];
                        IF sum > max sum THEN
                                max sum := sum;
                                begin max := begin;
                                end max := end
                        FI
                OD
        OD;
 
        FOR i FROM begin max TO end max DO
                print(a[i])
        OD
 
)

Output:

         +3         +5         +6         -2         -1         +4

[edit] AutoHotkey

classic algorithm:

seq = -1,-2,3,5,6,-2,-1,4,-4,2,-1
max := sum := start := 0
Loop Parse, seq, `,
   If (max < sum+=A_LoopField)
      max := sum, a := start, b := A_Index
   Else If sum <= 0
      sum := 0, start := A_Index
; read out the best subsequence
Loop Parse, seq, `,
   s .= A_Index > a && A_Index <= b ? A_LoopField "," : ""
MsgBox % "Max = " max "`n[" SubStr(s,1,-1) "]"

[edit] C

#include <stdio.h>
 
int main()
{
        int a[] = {-1 , -2 , 3 , 5 , 6 , -2 , -1 , 4 , -4 , 2 , -1};
        int length = 11;
 
        int begin, end, beginmax, endmax, maxsum, sum, i;
 
        sum = 0;
        beginmax = 0;
        endmax = -1;
        maxsum = 0;
 
 
        for (begin=0; begin<length; begin++) {
                sum = 0;
                for(end=begin; end<length; end++) {
                        sum += a[end];
                        if(sum > maxsum) {
                                maxsum = sum;
                                beginmax = begin;
                                endmax = end;
                        }
                }
        }
 
        for(i=beginmax; i<=endmax; i++) {
                printf("%d\n", a[i]);
        }
 
        return 0;
}

[edit] C++

#include <utility>   // for std::pair
#include <iterator>  // for std::iterator_traits
#include <iostream>  // for std::cout
#include <ostream>   // for output operator and std::endl
#include <algorithm> // for std::copy
#include <iterator>  // for std::output_iterator
 
// Function template max_subseq
//
// Given a sequence of integers, find a subsequence which maximizes
// the sum of its elements, that is, the elements of no other single
// subsequence add up to a value larger than this one.
//
// Requirements:
// * ForwardIterator is a forward iterator
// * ForwardIterator's value_type is less-than comparable and addable
// * default-construction of value_type gives the neutral element
//   (zero)
// * operator+ and operator< are compatible (i.e. if a>zero and
//   b>zero, then a+b>zero, and if a<zero and b<zero, then a+b<zero)
// * [begin,end) is a valid range
//
// Returns:
//   a pair of iterators describing the begin and end of the
//   subsequence
template<typename ForwardIterator>
 std::pair<ForwardIterator, ForwardIterator>
 max_subseq(ForwardIterator begin, ForwardIterator end)
{
  typedef typename std::iterator_traits<ForwardIterator>::value_type
    value_type;
 
  ForwardIterator seq_begin = begin, seq_end = seq_begin;
  value_type seq_sum = value_type();
  ForwardIterator current_begin = begin;
  value_type current_sum = value_type();
 
  value_type zero = value_type();
 
  for (ForwardIterator iter = begin; iter != end; ++iter)
  {
    value_type value = *iter;
    if (zero < value)
    {
      if (current_sum < zero)
      {
        current_sum = zero;
        current_begin = iter;
      }
    }
    else
    {
      if (seq_sum < current_sum)
      {
        seq_begin = current_begin;
        seq_end = iter;
        seq_sum = current_sum;
      }
    }
    current_sum += value;
  }
 
  if (seq_sum < current_sum)
  {
    seq_begin = current_begin;
    seq_end = end;
    seq_sum = current_sum;
  }
 
  return std::make_pair(seq_begin, seq_end);
}
 
// the test array
int array[] = { -1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1 };
 
// function template to find the one-past-end pointer to the array
template<typename T, int N> int* end(T (&arr)[N]) { return arr+N; }
 
int main()
{
  // find the subsequence
  std::pair<int*, int*> seq = max_subseq(array, end(array));
 
  // output it
  std::copy(seq.first, seq.second, std::ostream_iterator<int>(std::cout, " "));
  std::cout << std::endl;
 
  return 0;
}

[edit] Common Lisp

Linear version returns the maximum subsequence sum, the subsequence with the maximum sum, and start and end indices for the subsequence within the original sequence. Based on the implementation at Word Aligned. Leading zeroes aren't trimmed from the subsequence.

(defun max-subseq (list)
  (let ((best-sum 0) (current-sum 0) (end 0))
    ;; determine the best sum, and the end of the max subsequence
    (do ((list list (rest list))
         (i 0 (1+ i)))
        ((endp list))
      (setf current-sum (max 0 (+ current-sum (first list))))
      (when (> current-sum best-sum)
        (setf end i
              best-sum current-sum)))
    ;; take the subsequence of list ending at end, and remove elements
    ;; from the beginning until the subsequence sums to best-sum.
    (let* ((sublist (subseq list 0 (1+ end)))
           (sum (reduce #'+ sublist)))
      (do ((start 0 (1+ start))
           (sublist sublist (rest sublist))
           (sum sum (- sum (first sublist))))
          ((or (endp sublist) (eql sum best-sum))
           (values best-sum sublist start (1+ end)))))))

For example,

> (max-subseq '(-1 -2 -3 -4 -5))
0
NIL
1
1

> (max-subseq '(0 1 2 -3 3 -1 0 -4 0 -1 -4 2))
3
(0 1 2)
0
3

[edit] D

Adapted from the Python version:

import std.stdio: writefln;
 
T[] maxSubseq(T)(T[] sequence) {
    int start = -1, end = -1;
    T maxsum, sum;
 
    foreach (i, x; sequence) {
        sum += x;
        if (maxsum < sum) {
            maxsum = sum;
            end = i;
        } else if (sum < 0) {
            sum = 0;
            start = i;
        }
    }
 
    if (start <= end && start >= 0 && end >= 0)
        return sequence[start + 1 .. end + 1];
    else
        return null;
}
 
void main() {
    auto a1 = [-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1];
    writefln("Maximal subsequence: ", maxSubseq(a1));
 
    auto a2 = [-1, -2, -3, -5, -6, -2, -1, -4, -4, -2, -1];
    writefln("Maximal subsequence: ", maxSubseq(a2));
}

Sample result:

Maximal subsequence: [3,5,6,-2,-1,4]
Maximal subsequence: []

It can be written a version that accepts any iterable too.

[edit] E

This implementation tests every combination, but it first examines the sequence to reduce the number of combinations tried: We need not consider beginning the subsequence at any point which is not the beginning, or a change from negative to positive. We need not consider ending the subsequence at any point which is not the end, or a change from positive to negative. (Zero is moot and treated as negative.)

This algorithm is therefore $O (n m 2)$ where $n$ is the size of the sequence and $m$ is the number of sign changes in the sequence. I think it could be improved to $O (n + m 2)$ by recording the positive and negative intervals' sums during the initial pass and accumulating the sum of those sums in the inner for loop.

maxSubseq returns both the maximum sum found, and the interval of indexes which produces it.

pragma.enable("accumulator")
 
def maxSubseq(seq) {
  def size := seq.size()
 
  # Collect all intervals of indexes whose values are positive
  def intervals := {
    var intervals := []
    var first := 0
    while (first < size) {
      var next := first
      def seeing := seq[first] > 0
      while (next < size && (seq[next] > 0) == seeing) {
        next += 1
      }
      if (seeing) { # record every positive interval
        intervals with= first..!next
      }
      first := next
    }
    intervals
  }
 
  # For recording the best result found
  var maxValue := 0
  var maxInterval := 0..!0
 
  # Try all subsequences beginning and ending with such intervals.
  for firstIntervalIx => firstInterval in intervals {
    for lastInterval in intervals(firstIntervalIx) {
      def interval :=
        (firstInterval.getOptStart())..!(lastInterval.getOptBound())
      def value :=
        accum 0 for i in interval { _ + seq[i] }
      if (value > maxValue) {
        maxValue := value
        maxInterval := interval
      }
    }
  }
 
  return ["value" => maxValue,
          "indexes" => maxInterval]
}

def seq := [-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1]
def [=> value, => indexes] := maxSubseq(seq)
println(`$\
Sequence: $seq
Maximum subsequence sum: $value
Indexes: ${indexes.getOptStart()}..${indexes.getOptBound().previous()}
Subsequence: ${seq(indexes.getOptStart(), indexes.getOptBound())}
`)

[edit] Forth

2variable best
variable best-sum
 
: sum ( array len -- sum )
  0 -rot cells over + swap do i @ + cell +loop ;
 
: max-sub ( array len -- sub len )
  over 0 best 2!  0 best-sum !
  dup 1 do                  \ foreach length
    2dup i - cells over + swap do   \ foreach start
      i j sum
      dup best-sum @ > if
        best-sum !
        i j best 2!
      else drop then
    cell +loop
  loop
  2drop best 2@ ;
 
: .array  ." [" dup 0 ?do over i cells + @ . loop ." ] = " sum . ;
 
create test -1 , -2 , 3 , 5 , 6 , -2 , -1 , 4 , -4 , 2 , -1 ,
 
test 11 max-sub .array    \ [3 5 6 -2 -1 4 ] = 15

[edit] Fortran

Works with: Fortran version 95 and later

program MaxSubSeq
  implicit none
 
  integer, parameter :: an = 11
  integer, dimension(an) :: a = (/ -1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1 /)
 
  integer, dimension(an,an) :: mix
  integer :: i, j
  integer, dimension(2) :: m
 
  forall(i=1:an,j=1:an) mix(i,j) = sum(a(i:j))
  m = maxloc(mix)
  ! a(m(1):m(2)) is the wanted subsequence
  print *, a(m(1):m(2))
 
end program MaxSubSeq

[edit] Haskell

Naive approach which tests all possible subsequences, as in a few of the other examples:

import Data.List (inits, tails, maximumBy)
import Data.Ord (comparing)
 
subseqs :: [a] -> [[a]]
subseqs = concatMap inits . tails
 
maxsubseq :: (Ord a, Num a) => [a] -> [a]
maxsubseq = maximumBy (comparing sum) . subseqs

For fun, this is in point-free style and doesn't use loops.

Secondly, the linear time constant space approach:

maxsubseq xs = loop (0,0,xs) (0,0,xs) xs where
  loop (s,n,xs) _ [] = take n xs
  loop best@(bsum,_,_) (s,n,ys) (x:xs) 
    | s' < 0     = loop best (0,0,xs) xs
    | s' > bsum  = loop next next xs
    | otherwise  = loop best next xs
    where 
      s'   = x + s
      n'   = n + 1
      next = n' `seq` (s',n',ys)

[edit] J

maxss=: monad define
AS =. ;(|:&.>) a:, ((] #/"_1 1:) [: >: i.)&.> >: i. #y
IM =. I.@:(>./ = ]) AS (+/ . *) y
y #~ ;{. IM{AS
)

y is the input vector, an integer list.
AS means "all sub-sequences." It is a binary table. Each row indicates one sub-sequence; the count of columns equals the length of the input.
IM means "indices of maxima." It is a list of locations in AS where the corresponding sum is largest.
Totals for the subsequences are calculated by the phrase 'AS (+/ . *) y' which is the inner product of the binary table with the input vector.
All solutions are found but only one is returned, to fit the output requirement. If zero is the maximal sum the empty array is always returned, although sub-sequences of positive length (comprised of zeros) might be more interesting.

[edit] Java

Works with: Java version 1.5+ This is not a particularly efficient solution, but it gets the job done.

The method nextChoices was modified from an RIT CS lab.

import java.util.Scanner;
import java.util.ArrayList;
 
public class Sub{
    private static int[] indices;
 
    public static void main(String[] args){
        ArrayList<Long> array= new ArrayList<Long>(); //the main set
        Scanner in = new Scanner(System.in);
        while(in.hasNextLong()) array.add(in.nextLong());
        long highSum= Long.MIN_VALUE;//start the sum at the lowest possible value
        ArrayList<Long> highSet= new ArrayList<Long>();
        //loop through all possible subarray sizes including 0
        for(int subSize= 0;subSize<= array.size();subSize++){
            indices= new int[subSize];
            for(int i= 0;i< subSize;i++) indices[i]= i;
            do{
                long sum= 0;//this subarray sum variable
                ArrayList<Long> temp= new ArrayList<Long>();//this subarray
                //sum it and save it
                for(long index:indices) {sum+= array.get(index); temp.add(array.get(index));}
                if(sum > highSum){//if we found a higher sum
                    highSet= temp;    //keep track of it
                    highSum= sum;
                }
            }while(nextIndices(array));//while we haven't tested all subarrays
        }
        System.out.println("Sum: " + highSum + "\nSet: " + 
        		highSet);
    }
    /**
     * Computes the next set of choices from the previous. The
     * algorithm tries to increment the index of the final choice
     * first. Should that fail (index goes out of bounds), it
     * tries to increment the next-to-the-last index, and resets
     * the last index to one more than the next-to-the-last.
     * Should this fail the algorithm keeps starting at an earlier
     * choice until it runs off the start of the choice list without
     * Finding a legal set of indices for all the choices.
     *
     * @return true unless all choice sets have been exhausted.
     * @author James Heliotis
     */
 
    private static boolean nextIndices(ArrayList<Long> a) {
        for(int i= indices.length-1;i >= 0;--i){
            indices[i]++;
            for(int j=i+1;j < indices.length;++j){
                indices[j]= indices[j - 1] + 1;//reset the last failed try
            }
            if(indices[indices.length - 1] < a.size()){//if this try went out of bounds
                return true;
            }
        }
        return false;
    }
}

This one runs in linear time, and isn't generalized.

private static int BiggestSubsum(int[] t) {
    int sum = 0;
    int maxsum = 0;
 
    for (int i : t) {
        sum += i;
        if (sum < 0)
            sum = 0;
        maxsum = sum > maxsum ? sum : maxsum;
    }        
    return maxsum;
}

[edit] Lua

 
function sumt(t, start, last) return start <= last and t[start] + sumt(t, start+1, last) or 0 end
function maxsub(ary, idx)
  local idx = idx or 1
  if not ary[idx] then return {} end
  local maxsum, last = 0, idx
  for i = idx, #ary do
    if sumt(ary, idx, i) > maxsum then maxsum, last = sumt(ary, idx, i), i end
  end
  local v = maxsub(ary, idx + 1)
  if maxsum < sumt(v, 1, #v) then return v end
  local ret = {}
  for i = idx, last do ret[#ret+1] = ary[i] end
  return ret
end

[edit] M4

divert(-1)
define(`setrange',`ifelse(`$3',`',$2,`define($1[$2],$3)`'setrange($1,
   incr($2),shift(shift(shift($@))))')')
define(`asize',decr(setrange(`a',1,-1,-2,3,5,6,-2,-1,4,-4,2,-1)))
define(`get',`defn(`$1[$2]')')
define(`for',
   `ifelse($#,0,``$0'',
   `ifelse(eval($2<=$3),1,
   `pushdef(`$1',$2)$4`'popdef(`$1')$0(`$1',incr($2),$3,`$4')')')')
define(`maxsum',0)
for(`x',1,asize,
   `define(`sum',0)`'for(`y',x,asize,
      `define(`sum',eval(sum+get(`a',y)))`'ifelse(eval(sum>maxsum),1,
         `define(`maxsum',sum)`'define(`xmax',x)`'define(`ymax',y)')')')
divert
for(`x',xmax,ymax,`get(`a',x) ')

[edit] Mathematica

[edit] Method 1

First we define 2 functions, one that gives all possibles subsequences (as a list of lists of indices) for a particular length. Then another extract those indices adds them up and looks for the largest sum.

Sequences[m_]:=Prepend[Flatten[Table[Partition[Range[m],n,1],{n,m}],1],{}]
MaximumSubsequence[x_List]:=Module[{sums},
 sums={x[[#]],Total[x[[#]]]}&/@Sequences[Length[x]];
 First[First[sums[[Ordering[sums,-1,#1[[2]]<#2[[2]]&]]]]]
]

[edit] Method 2

MaximumSubsequence[x_List]:=Last@SortBy[Flatten[Table[x[[a;;b]], {b,Length[x]}, {a,b}],1],Total]

[edit] Examples

MaximumSubsequence[{-1,-2,3,5,6,-2,-1,4,-4,2,-1}]
MaximumSubsequence[{2,4,5}]
MaximumSubsequence[{2,-4,3}]
MaximumSubsequence[{4}]
MaximumSubsequence[{}]

gives back:

{3,5,6,-2,-1,4}
{2,4,5}
{3}
{4}
{}

[edit] OCaml

let maxsubseq =
  let rec loop sum seq maxsum maxseq = function
    | [] -> maxsum, List.rev maxseq
    | x::xs ->
        let sum = sum + x
        and seq = x :: seq in
          if sum < 0 then
            loop 0 [] maxsum maxseq xs
          else if sum > maxsum then
            loop sum seq sum seq xs
          else
            loop sum seq maxsum maxseq xs
  in
    loop 0 [] 0 []
 
let _ =
  maxsubseq [-1 ; -2 ; 3 ; 5 ; 6 ; -2 ; -1 ; 4; -4 ; 2 ; -1]

This returns a pair of the maximum sum and (one of) the maximum subsequence(s).

[edit] Oz

declare
  fun {MaxSubSeq Xs}
 
     fun {Step [Sum0 Seq0 MaxSum MaxSeq] X}
        Sum = Sum0 + X
        Seq = X|Seq0
     in
        if Sum > MaxSum then
           %% found new maximum
           [Sum Seq Sum Seq]
        elseif Sum < 0 then
           %% discard negative subseqs
           [0 nil MaxSum MaxSeq]
        else
           [Sum Seq MaxSum MaxSeq]
        end
     end
 
     [_ _ _ MaxSeq] = {FoldL Xs Step [0 nil 0 nil]}
  in
     {Reverse MaxSeq}
  end
in
  {Show {MaxSubSeq [~1 ~2 3 5 6 ~2 ~1 4 ~4 2 1]}}

[edit] Perl

use strict;
 
my @a = (-1 , -2 , 3 , 5 , 6 , -2 , -1 , 4 , -4 , 2 , -1);
 
my @maxsubarray;
my $maxsum = 0;
 
foreach my $begin (0..$#a) {
        foreach my $end ($begin..$#a) {
                my $sum = 0;
                $sum += $_ foreach @a[$begin..$end];
                if($sum > $maxsum) {
                        $maxsum = $sum;
                        @maxsubarray = @a[$begin..$end];
                }
        }
}
 
print "@maxsubarray\n";

[edit] Perl 6

Translation of: Python

Works with: Rakudo version #21 "Seattle"

sub maxsubseq (*@a) {
    my ($start, $end, $sum, $maxsum) = -1, -1, 0, 0;
    for @a.kv -> $i, $x {
        $sum += $x;
        if $maxsum < $sum {
            $maxsum, $end = $sum, $i;
        }
        elsif $sum < 0 {
            $sum, $start = 0, $i;
        }
    }
    return @a[$start ^.. $end];
}

[edit] PicoLisp

(maxi '((L) (apply + L))
   (mapcon '((L) (maplist reverse (reverse L)))
      (-1 -2 3 5 6 -2 -1 4 -4 2 -1) ) )

Output:

-> (3 5 6 -2 -1 4)

[edit] PureBasic

If OpenConsole()
  Define s$, a, b, p1, p2, sum, max, dm=(?EndOfMyData-?MyData)
  Dim Seq.i(dm/SizeOf(Integer))
  CopyMemory(?MyData,@seq(),dm)
 
  For a=0 To ArraySize(seq())
    sum=0
    For b=a To ArraySize(seq())
      sum+seq(b)
      If sum>max
        max=sum
        p1=a
        p2=b
      EndIf
    Next
  Next
 
  For a=p1 To p2
    s$+str(seq(a))
    If a<p2 
      s$+"+"
    EndIf
  Next
  PrintN(s$+" = "+str(max))
 
  Print("Press ENTER to quit"): Input()
  CloseConsole()
EndIf
 
 
DataSection
  MyData:
  Data.i  -1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1
  EndOfMyData:
EndDataSection

[edit] Python

Naive, inefficient but really simple solution which tests all possible subsequences, as in a few of the other examples:

def maxsubseq(seq):
  return max((seq[begin:end] for begin in xrange(len(seq)+1)
                             for end in xrange(begin, len(seq)+1)),
             key=sum)

Classic linear-time constant-space solution based on algorithm from "Programming Pearls" book.

def maxsum(sequence):
    """Return maximum sum."""
    maxsofar, maxendinghere = 0, 0
    for x in sequence:
        # invariant: ``maxendinghere`` and ``maxsofar`` are accurate for ``x[0..i-1]``          
        maxendinghere = max(maxendinghere + x, 0)
        maxsofar = max(maxsofar, maxendinghere)
    return maxsofar

Adapt the above-mentioned solution to return maximizing subsequence. See http://www.java-tips.org/java-se-tips/java.lang/finding-maximum-contiguous-subsequence-sum-using-divide-and-conquer-app.html

def maxsumseq(sequence):
    start, end = -1, -1
    maxsum_, sum_ = 0, 0
    for i, x in enumerate(sequence):
        sum_ += x
        if maxsum_ < sum_: 
            maxsum_ = sum_
            end = i
        elif sum_ < 0:
            sum_ = 0
            start = i
    assert maxsum_ == maxsum(sequence) 
    assert maxsum_ == sum(sequence[start + 1:end + 1])
    return sequence[start + 1:end + 1]

Modify ``maxsumseq()`` to allow any iterable not just sequences.

def maxsumit(iterable):
    seq = []
    start, end = -1, -1
    maxsum_, sum_ = 0, 0
    for i, x in enumerate(iterable):
        seq.append(x); sum_ += x
        if maxsum_ < sum_: 
            maxsum_ = sum_
            end = i
        elif sum_ < 0:
            seq = []; sum_ = 0
            start = i
    assert maxsum_ == sum(seq[:end - start])
    return seq[:end - start]

Elementary tests:

f = maxsumit
assert f([]) == []
assert f([-1]) == []
assert f([0])  == []
assert f([1])       == [1]
assert f([1, 0])    == [1]
assert f([0, 1])    == [0, 1]   
assert f([0, 1, 0]) == [0, 1]   
assert f([2])         == [2]
assert f([2, -1])     == [2]
assert f([-1, 2])     == [2]
assert f([-1, 2, -1]) == [2]
assert f([2, -1, 3])         == [2, -1, 3]
assert f([2, -1, 3, -1])     == [2, -1, 3] 
assert f([-1, 2, -1, 3])     == [2, -1, 3]
assert f([-1, 2, -1, 3, -1]) == [2, -1, 3]

[edit] R

#Loosely translated from C; 'length' renamed to 'len', 'end' renamed to 'end.', since the former are functions in R
 maxsubseq <- function(x)
 {
   maxsum <- 0
   bestsubseq <- c()
   len <- length(x)
   for(begin in 1:len)
   {
      for(end. in begin:len)
      {
         currentsum <- sum(x[begin:end.])
         if(currentsum > maxsum)
         {
            maxsum <- currentsum
            bestsubseq <- x[begin:end.]
         }
      }
   }
   list(maxsum=maxsum, bestsubseq=bestsubseq)
 }
 
 maxsubseq(c(-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1))

[edit] Ruby

Answer is stored in "slice":

max, slice, numbers = 0, [], [-1, -2, -1 , 4, 1, -2, -3, -1]
 
numbers.each_with_index do |n,i|
  for j in (i...numbers.length)
    sum = numbers[i..j].inject(0) {|x, sum| sum += x}
    if sum > max
      max = sum
      slice = numbers[i..j]
    end
  end
end

[edit] Scala

Works with: Scala version 2.8

The first solution solves the problem as specified, the second gives preference to the longest subsequence in case of ties. They are both vulnerable to integer overflow.

The third solution accepts any type N for which there's a Numeric[N], which includes all standard numeric types, and can be extended to include user defined numeric classes.

The last solution keeps to linear time by increasing complexity slightly.

def maxSubseq(l: List[Int]) = l.scanRight(Nil : List[Int]) {
  case (el, acc) if acc.sum + el < 0 => Nil
  case (el, acc)                     => el :: acc
} max Ordering.by((_: List[Int]).sum)
 
def biggestMaxSubseq(l: List[Int]) = l.scanRight(Nil : List[Int]) {
  case (el, acc) if acc.sum + el < 0 => Nil
  case (el, acc)                     => el :: acc
} max Ordering.by((ss: List[Int]) => (ss.sum, ss.length))
 
def biggestMaxSubseq[N](l: List[N])(implicit n: Numeric[N]) = {
  import n._
  l.scanRight(Nil : List[N]) {
    case (el, acc) if acc.sum + el < zero => Nil
    case (el, acc)                        => el :: acc
  } max Ordering.by((ss: List[N]) => (ss.sum, ss.length))
}
 
def linearBiggestMaxSubseq[N](l: List[N])(implicit n: Numeric[N]) = {
  import n._
  l.scanRight((zero, Nil : List[N])) {
    case (el, (acc, _)) if acc + el < zero => (zero, Nil)
    case (el, (acc, ss))                   => (acc + el, el :: ss)
  } max Ordering.by((t: (N, List[N])) => (t._1, t._2.length)) _2
}

[edit] Scheme

(define (maxsubseq in)
  (let loop
    ((_sum 0) (_seq (list)) (maxsum 0) (maxseq (list)) (l in))
    (if (null? l)
        (cons maxsum (reverse maxseq))
        (let* ((x (car l)) (sum (+ _sum x)) (seq (cons x _seq)))
          (if (> sum 0)
              (if (> sum maxsum)
                  (loop sum seq    sum    seq (cdr l))
                  (loop sum seq maxsum maxseq (cdr l)))
              (loop 0 (list) maxsum maxseq (cdr l)))))))

This returns a cons of the maximum sum and (one of) the maximum subsequence(s).

[edit] Standard ML

val maxsubseq = let
  fun loop (_, _, maxsum, maxseq) [] = (maxsum, rev maxseq)
    | loop (sum, seq, maxsum, maxseq) (x::xs) = let
        val sum = sum + x
        val seq = x :: seq
      in
        if sum < 0 then
          loop (0, [], maxsum, maxseq) xs
        else if sum > maxsum then
          loop (sum, seq, sum, seq) xs
        else
          loop (sum, seq, maxsum, maxseq) xs
      end
in
  loop (0, [], 0, [])
end;
 
maxsubseq [~1, ~2, 3, 5, 6, ~2, ~1, 4, ~4, 2, ~1]