Greatest subsequential sum
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.
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.
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;
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]);
}
}
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;
}
D
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
J
maxss=: 3 : 0
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.
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);
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