Greatest subsequential sum

Greatest subsequential sum
You are encouraged to solve this task according to the task description, using any language you may know.

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.

Ada

<lang 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;</lang>

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

<lang algol68>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

)</lang> Output:

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

AutoHotkey

classic algorithm: <lang AutoHotkey>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) "]" </lang>

C

<lang 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;

}</lang>

C++

<lang cpp>#include <utility> // for std::pair

1. include <iterator> // for std::iterator_traits
2. include <iostream> // for std::cout
3. include <ostream> // for output operator and std::endl
4. include <algorithm> // for std::copy
5. 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;

}</lang>

C#

The challange <lang csharp>using System;

namespace Tests_With_Framework_4 {

   class Program
   {
       static void Main(string[] args)
       {
           int[] integers = { -1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1 }; int length = integers.Length;
           int maxsum, beginmax, endmax, sum; maxsum = beginmax = sum = 0; endmax = -1;

           for (int i = 0; i < length; i++)
           {
               sum = 0;
               for (int k = i; k < length; k++)
               {
                   sum += integers[k];
                   if (sum > maxsum)
                   {
                       maxsum = sum;
                       beginmax = i;
                       endmax = k;
                   }
               }
           }

           for (int i = beginmax; i <= endmax; i++)
               Console.WriteLine(integers[i]);

           Console.ReadKey();
       }
   }

} </lang>

Clojure

Translation of: Haskell

Naive algorithm:

<lang clojure>(defn max-subseq-sum [coll]

 (->> (take-while seq (iterate rest coll)) ; tails
      (mapcat #(reductions conj [] %)) ; inits
      (apply max-key #(reduce + %)))) ; max sum</lang>

Sample output: <lang clojure>user> (max-subseq-sum [-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1]) [3 5 6 -2 -1 4]</lang>

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.

<lang lisp>(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)))))))</lang>

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

D

Adapted from the Python version:

<lang d>import std.stdio: writeln;

T[] maxSubseq(T)(T[] sequence) {

   int maxSum, thisSum, i;
   int start = 0, end = -1;

   foreach (j, x; sequence) {
       thisSum += x;
       if (thisSum < 0) {
           i = j + 1;
           thisSum = 0;
       } else if (thisSum > maxSum) {
           maxSum = thisSum;
           start = i;
           end   = j;
       }
   }

   if (start <= end && start >= 0 && end >= 0)
       return sequence[start .. end + 1];
   else
       return null;

}

void main() {

   auto a1 = [-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1];
   writeln("Maximal subsequence: ", maxSubseq(a1));

   auto a2 = [-1, -2, -3, -5, -6, -2, -1, -4, -4, -2, -1];
   writeln("Maximal subsequence: ", maxSubseq(a2));

}</lang> Output:

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

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(nm^{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.

<lang e>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]

}</lang>

<lang e>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())} `)</lang>

Forth

<lang 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</lang>

Fortran

Works with: Fortran version 95 and later

<lang fortran>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</lang>

Go

<lang go> package main

import (

   "fmt"

)

func gss(s []int) []int {

   var best, start, end, sum, sumStart int
   for i, x := range s {
       sum += x
       switch {
       case sum > best:
           best = sum
           start = sumStart
           end = i+1
       case sum < 0:
           sum = 0
           sumStart = i+1
       }
   }
   return s[start:end]

}

func main() {

   fmt.Println(gss([]int{-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1}))

} </lang>

Haskell

Naive approach which tests all possible subsequences, as in a few of the other examples. For fun, this is in point-free style and doesn't use loops: <lang haskell>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

main = print $ maxsubseq [-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1] </lang> Secondly, the linear time constant space approach: <lang haskell>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)

main = print $ maxsubseq [-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1]</lang>

Icon and Unicon

<lang Icon>procedure main() L1 := [-1,-2,3,5,6,-2,-1,4,-4,2,-1] # sample list L  := [-1,1,2,3,4,-11]|||L1 # prepend a local maximum into the mix write(ximage(maxsubseq(L))) end

link ximage # to show lists

procedure maxsubseq(L) #: return the subsequence of L with maximum positive sum local i,maxglobal,maxglobalI,maxlocal,maxlocalI

maxglobal := maxlocal := 0 # global and local maxima

every i := 1 to *L do {

  if (maxlocal := max(maxlocal +L[i],0)) > 0 then 
     if /maxlocalI then maxlocalI := [i,i] else maxlocalI[2] := i   # local maxima subscripts
  else maxlocalI := &null                                           # reset subsequence
  if maxglobal <:= maxlocal then                                    # global maxima
     maxglobalI := copy(maxlocalI)
  }

return L[(\maxglobalI)[1]:maxglobalI[2]] | [] # return sub-sequence or empty list end</lang>

J

<lang j>maxss=: monad define

AS =. 0,; <:/~@i.&.> #\y
MX =. (= >./) AS +/ . * y
y #~ {. MX#AS

)</lang>

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.
MX means "maxima." It is the first location 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.
Example use: <lang j> maxss _1 _2 3 5 6 _2 _1 4 _4 2 _1 3 5 6 _2 _1 4</lang>

Note: if we just want the sum of the maximum subsequence,and are not concerned with the subsequence itself, we can use:

<lang j>maxs=: [:>./(0>.+)/\.</lang>

Example use:

<lang> maxs _1 _2 3 5 6 _2 _1 4 _4 2 _1 15</lang>

This suggests a variant:

<lang j>maxSS=:monad define

 sums=: (0>.+)/\. y
 start=: sums i. max=: >./ sums
 max (] {.~ #@] |&>: (= +/\) i. 1:) y}.~start

)</lang>

or

<lang j>maxSS2=:monad define

 start=. (i. >./) (0>.+)/\. y
 ({.~ # |&>: [: (i.>./@,&0) +/\)  y}.~start

)</lang>

These variants are considerably faster than the first implementation, on long sequences.

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. <lang java>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;
   }

}</lang>

This one runs in linear time, and isn't generalized. <lang java>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;

}</lang>

Lua

<lang 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 </lang>

M4

<lang 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) ')</lang>

Mathematica

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. <lang Mathematica>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,#12<#22&]]]]]

]</lang>

Method 2

<lang Mathematica>MaximumSubsequence[x_List]:=Last@SortBy[Flatten[Table[xa;;b, {b,Length[x]}, {a,b}],1],Total]</lang>

Examples

<lang Mathematica>MaximumSubsequence[{-1,-2,3,5,6,-2,-1,4,-4,2,-1}] MaximumSubsequence[{2,4,5}] MaximumSubsequence[{2,-4,3}] MaximumSubsequence[{4}] MaximumSubsequence[{}]</lang> gives back: <lang Mathematica>{3,5,6,-2,-1,4} {2,4,5} {3} {4} {}</lang>

OCaml

<lang 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]</lang>

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

Oz

<lang 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]}}</lang>

Perl

<lang 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";</lang>

Perl 6

Translation of: Python

Works with: Rakudo version #21 "Seattle"

<lang perl6>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];

}</lang>

Another solution, not translated from any other language:

For each starting position, we calculate all the subsets starting at that position. They are combined with the best subset ($max_subset) from previous loops, to form (@subsets). The best of those @subsets is saved at the new $max_subset.

Consuming the array (.shift) allows us to skip tracking the starting point; it is always 0.

The empty sequence is used to initialize $max_subset, which fufills the "all negative" requirement of the problem.

Note that once the triangular comma bug is resolved, the inner-loop subset calculation line can be shortened to "my @subsets = [\,] @a;". <lang perl6>sub max_sub-seq ( *@a ) {

   my $max_subset = [];
   while @a {
       my @subsets = @a.keys.map: { [ @a[0..$_] ] };
       @subsets.push($max_subset);
       $max_subset = @subsets.max: { [+] .list };
       @a.shift;
   }

   return $max_subset;

}

max_sub-seq( -1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1 ).perl.say; max_sub-seq( -2, -2, -1, 3, 5, 6, -1, 4, -4, 2, -1 ).perl.say; max_sub-seq( -2, -2, -1, -3, -5, -6, -1, -4, -4, -2, -1 ).perl.say; </lang>

Output:

[3, 5, 6, -2, -1, 4]
[3, 5, 6, -1, 4]
[]

PicoLisp

<lang PicoLisp>(maxi '((L) (apply + L))

  (mapcon '((L) (maplist reverse (reverse L)))
     (-1 -2 3 5 6 -2 -1 4 -4 2 -1) ) )</lang>

Output:

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

PureBasic

<lang 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</lang>

Python

Naive, inefficient but really simple solution which tests all possible subsequences, as in a few of the other examples: <lang python>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)</lang>

Classic linear-time constant-space solution based on algorithm from "Programming Pearls" book. <lang python>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</lang>

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 <lang python>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]</lang>

Modify ``maxsumseq()`` to allow any iterable not just sequences. <lang python>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]</lang>

Elementary tests: <lang python>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]</lang>

R

<lang 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))</lang>

REXX

version 1

This REXX version will find the shortest greatest continous subsequence sum. <lang rexx> /*REXX program to find sum of the greatest continous subsequence sum. */

arg @ /*get the arugment LIST (if any).*/ say 'words='words(@) 'list='@ /*show WORDS and LIST to console.*/ say sum=word(@,1) /*a "starter" sum (of a sequence)*/ w=words(@) /*number of words in the list. */ at=1 /*where the sequence starts at. */ L=0 /*the length of the sequence. */

/*───────────────────────────────────────process the list───────────────*/

 do j=1 for w;  f=word(@,j)

       do k=j to w; s=f

             do m=j+1 to k
             s=s+word(@,m)
             end   /*m*/

       if s>sum then do; sum=s; at=j; L=k-j+1; end
       end         /*k*/

 end               /*j*/

/*──────────────────────────────────────────────────────────────────────*/

seq=subword(@,at,L) if seq== then seq="[NULL]" sum=word(sum 0,1) say 'sum='sum/1 "sequence="seq </lang> Output when the following was used for the list:

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

words=11 list=-1 -2 3 5 6 -2 -1 4 -4 2 -1

sum=15 sequence=3 5 6 -2 -1 4

Output when the following was used for the list:

1 2 3 4 -777 1 2 3 4 0 0

words=12 list=1 2 3 4 0 -777 1 2 3 4 0 0

sum=10 sequence=1 2 3 4

version 2

This REXX version will find the longest greatest continous subsequence sum. <lang rexx> /*REXX program to find sum of the greatest continous subsequence sum. */

arg @ /*get the arugment LIST (if any).*/ say 'words='words(@) 'list='@ /*show WORDS and LIST to console.*/ say sum=word(@,1) /*a "starter" sum (of a sequence)*/ w=words(@) /*number of words in the list. */ at=1 /*where the sequence starts at. */ L=0 /*the length of the sequence. */

/*───────────────────────────────────────process the list───────────────*/

 do j=1 for w;  f=word(@,j)

       do k=j to w; s=f

             do m=j+1 to k
             s=s+word(@,m)
             end   /*m*/

       _=k-j+1
       if (s==sum & _>L) | s>sum then do; sum=s; at=j; L=_; end
       end         /*k*/

 end               /*j*/

/*──────────────────────────────────────────────────────────────────────*/

seq=subword(@,at,L) if seq== then seq="[NULL]" sum=word(sum 0,1) say 'sum='sum/1 "sequence="seq </lang> Output:

Output when the following was used for the list:

1 2 3 4 -777 1 2 3 4 0 0

words=12 list=1 2 3 4 0 -777 1 2 3 4 0 0

sum=10 sequence=1 2 3 4 0 0

Ruby

Answer is stored in "slice": <lang ruby>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</lang>

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.

<lang scala>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

}</lang>

Scheme

<lang 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)))))))</lang>

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

Standard ML

<lang sml>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]</lang>

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

Tcl

<lang tcl>package require Tcl 8.5 set a {-1 -2 3 5 6 -2 -1 4 -4 2 -1}

1. from the Perl solution

proc maxsumseq1 {a} {

   set len [llength $a]
   set maxsum 0
   
   for {set start 0} {$start < $len} {incr start} {
       for {set end $start} {$end < $len} {incr end} {
           set sum 0
           incr sum [expr [join [lrange $a $start $end] +]]
           if {$sum > $maxsum} {
               set maxsum $sum
               set maxsumseq [lrange $a $start $end]
           }
       }
   }
   return $maxsumseq

}

1. from the Python solution

proc maxsumseq2 {sequence} {

   set start -1
   set end -1
   set maxsum_ 0
   set sum_ 0
   for {set i 0} {$i < [llength $sequence]} {incr i} {
       set x [lindex $sequence $i]
       incr sum_ $x
       if {$maxsum_ < $sum_} { 
           set maxsum_ $sum_
           set end $i
       } elseif {$sum_ < 0} {
           set sum_ 0
           set start $i
       }
   }
   assert {$maxsum_ == [maxsum $sequence]}
   assert {$maxsum_ == [sum [lrange $sequence [expr {$start + 1}] $end]]}
   return [lrange $sequence [expr {$start + 1}] $end]

}

proc maxsum {sequence} {

   set maxsofar 0
   set maxendinghere 0
   foreach x $sequence {
       set maxendinghere [expr {max($maxendinghere + $x, 0)}]
       set maxsofar [expr {max($maxsofar, $maxendinghere)}]
   }
   return $maxsofar

}

proc assert {condition {message "Assertion failed!"}} {

   if { ! [uplevel 1 [list expr $condition]]} {
       return -code error $message
   }

}

proc sum list {

   expr [join $list +]

}

puts "sequence: $a" puts "maxsumseq1: [maxsumseq1 $a]" puts [time {maxsumseq1 $a} 1000] puts "maxsumseq2: [maxsumseq2 $a]" puts [time {maxsumseq2 $a} 1000]</lang> outputs

sequence:  -1 -2 3 5 6 -2 -1 4 -4 2 -1
maxsumseq1: 3 5 6 -2 -1 4
367.041 microseconds per iteration
maxsumseq2: 3 5 6 -2 -1 4
74.623 microseconds per iteration

Ursala

This example solves the problem by the naive algorithm of testing all possible subsequences. <lang Ursala>#import std

1. import int

max_subsequence = zleq$^l&r/&+ *aayK33PfatPRTaq ^/~& sum:-0

1. cast %zL

example = max_subsequence <-1,-2,3,5,6,-2,-1,4,-4,2,-1> </lang> The general theory of operation is as follows.

• The max_subsequence function is a composition of three functions, one to generate the sequences, one to sum all of them, and one to pick out the one with the maximum sum.
• The function that sums all the sequences is * ^/~& sum:-0 which applies to every member of a list (by the * operator) and forms a pair (using the ^ operator) of the identity function (~&) of its argument, and the reduction (:-) of the sum over a list with a vacuous case result of 0.
• The function that picks out the maximum sum is zleq$^l&r/&, which uses the maximizing operator ($^) over a list of pairs with respect to the integer ordering relation (zleq) applied to the right sides of the pairs (&r), after which the left side (l) of the maximizing pair is extracted. The /& inserts an extra pair (<>,0) at the beginning of the list before searching it in case it's empty or has only negative sums.
• The function that generates all the sequences is ~&aayK33PfatPRTaq, which appears as a suffix of the * operator rather than being used explicitly.
• The sequence generating function is in the form of a recursive conditional (q) with predicate a, inductive case ayK33PfatPRT and base case a, meaning that in the base case of an empty list argument, the argument itself is returned.
• The inductive case, ayK33PfatPRT is a concatenation (T) of two functions ayK33 and fatPR
• The latter function, fatPR is a recursive call (R) of the enclosing recursive conditional (f) with the tail of the argument (at).
• The remaining function, ayK33 uses the triangle-squared combinator K33 of the list-lead operator y applied to the argument a.
• The list lead operator y by itself takes a non-empty list as an argument and returns a copy with the last item deleted.
• The triangle-squared combinator K33 constructs a function that takes an input list of a length $n$, constructs a list of $n$ copies of it, and applies its operand 0 times to the head, once to the head of tail, twice to the head of the tail of the tail, and so on. Hence, an operand of y will generate the list of all prefixes of a list.

output:

<3,5,6,-2,-1,4>