Greatest subsequential sum: Difference between revisions
Line 168: | Line 168: | ||
T subsum(T = int)(T[] a) { |
T subsum(T = int)(T[] a) { |
||
T sum = 0 ; |
|||
foreach(e ; a) |
|||
sum += e ; |
|||
return sum ; |
|||
} |
} |
||
T[] submax(T = int)(T[] a) { |
T[] submax(T = int)(T[] a) { |
||
T[] maxsub ; |
|||
T maxsum = T.min ; |
|||
for(int i = 0 ; i < a.length ; i++) |
|||
for(int j = i + 1 ; j <= a.length ; j++) |
|||
maxsum = (maxsum <= a[i..j].subsum()) ? (maxsub = a[i..j].dup).subsum() : maxsum ; |
|||
return (maxsum >= 0 ) ? maxsub : new T[0] ; |
|||
maxsub= a[i..j].dup ; |
|||
} |
|||
return maxsub ; |
|||
} |
} |
||
void main() { |
void main() { |
||
int[] array = [-1 , -2 , 3 , 5 , 6 , -2 , -1 , 4, -4 , 2 , -1] ; |
|||
writefln("sum of %s = %s", array.submax(), array.submax().subsum()) ; |
|||
array = [-1 , -2 , -3 , -5 , -6 , -2 , -1 , -4 , -4 , -2 , -1] ; |
|||
⚫ | |||
writefln("sum of %s = %s", array.submax(), array.submax().subsum()) ; |
|||
} |
|||
⚫ | |||
=={{header|Forth}}== |
=={{header|Forth}}== |
Revision as of 13:17, 31 January 2008
You are encouraged to solve this task according to the task description, using any language you may know.
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.
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
module submax; import std.stdio; T subsum(T = int)(T[] a) { T sum = 0 ; foreach(e ; a) sum += e ; return sum ; } T[] submax(T = int)(T[] a) { T[] maxsub ; T maxsum = T.min ; for(int i = 0 ; i < a.length ; i++) for(int j = i + 1 ; j <= a.length ; j++) maxsum = (maxsum <= a[i..j].subsum()) ? (maxsub = a[i..j].dup).subsum() : maxsum ; return (maxsum >= 0 ) ? maxsub : new T[0] ; } void main() { int[] array = [-1 , -2 , 3 , 5 , 6 , -2 , -1 , 4, -4 , 2 , -1] ; writefln("sum of %s = %s", array.submax(), array.submax().subsum()) ; array = [-1 , -2 , -3 , -5 , -6 , -2 , -1 , -4 , -4 , -2 , -1] ; writefln("sum of %s = %s", array.submax(), array.submax().subsum()) ; }
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