Greatest subsequential sum

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

Greatest subsequential sum is a programming puzzle. It lays out a problem which Rosetta Code users are encouraged to solve, using languages and techniques they know. Multiple approaches are not discouraged, so long as the puzzle guidelines are followed. For other Puzzles, see Category:Puzzles.

This task has been flagged for clarification. Code on this page in its current state may be flagged incorrect once this task has been clarified. See this page's Talk page for discussion.

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

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

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

Python

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] 

Ruby

class SubArray
  attr_accessor :start_i, :end_i, :sum, :neg_sum
  
  def initialize( s_i=0, e_i=nil, s=0, n=0 )
    @start_i = s_i
    @end_i   = e_i
    @sum     = s
    @neg_sum = n
  end

end

if $0==__FILE__: #MAIN
  
  array = [-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1]
  max = SubArray.new()
  tmp = SubArray.new()

  array.each_with_index do |el, i|
    if el > 0
      if tmp.neg_sum < 0 # this means we are in look-ahead mode and we just hit our first pos
        if ( tmp.sum + tmp.neg_sum + el ) > tmp.sum
          tmp.sum += ( tmp.neg_sum + el )
          tmp.end_i = i # extend our subarray to encompass the negs up to this pos
        else
          max = ( tmp.sum > max.sum ? tmp : max )
          tmp = SubArray.new( i ) # our tmp now starts with this pos
        end
      else
        tmp.sum += el   # add this to sum
        tmp.end_i = i   # extend our subarray
      end
    else
      tmp.neg_sum += el # let's find out if these negs are worth it...
    end
  end
  
  puts array[max.start_i..max.end_i].inspect
end

C

int main(int argc, char *argv[])
{
        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]);
        }
}

Perl

use strict;

my @a = (-1 , -2 , 3 , 5 , 6 , -2 , -1 , 4 , -4 , 2 , -1);
my $length = scalar @a;

my @maxsubarray;
my $maxsum = 0;

for my $begin (0..$length-1) {
        for my $end ($begin..$length-1) {
                my $sum = 0;
                map {$sum += $_} (@a[$begin..$end]);
                if($sum > $maxsum) {
                        $maxsum = $sum;
                        @maxsubarray = @a[$begin..$end];
                }
        }
}

print (join ' ', @maxsubarray);