Maximum subarray

From Rosetta Code

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.

Contents 1 Ada 2 C 3 C++ 4 D 5 Forth 6 Fortran 7 Haskell 8 J 9 Java 10 OCaml 11 Perl 12 Python 13 Ruby 14 Scheme

[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] 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]);
        }
}

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

[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] 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

Unless I am misunderstanding something about this problem, the subarray desired is the same as the subarray of all non-negative elements.

In ISO Fortran 90 or later use various Array syntax features, including the COUNT and PACK intrinsics:

  program max_subarray
     integer :: i
     integer, parameter :: n = 11
     integer, dimension(n) :: a = (/ -1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1 /)
     integer, dimension(n) :: index_count = (/ (i,i=1,n) /)
     integer, pointer, dimension(:) :: max_index, max_subarray
     integer :: max_size
     
     max_size = count( a >= 0 )                !size of the subarray
     allocate( max_index(max_size) )
     max_index = pack(index_count, a >= 0)     !indices of the elements of the subarray desired
     
       !  --- OR ---
     
     allocate( max_subarray(max_size) )
     max_subarray = pack(a, a >= 0)            !the actual subarray desired
  end program max_subarray

[edit] Haskell

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

 subseqs :: [a] -> [[a]]
 subseqs = concatMap (tail . inits) . tails
 
 maxsubseq :: (Ord a, Num a) => [a] -> [a]
 maxsubseq = maximumUnder sum . subseqs

For fun, this is in point-free style and doesn't use loops. However, it requires a function maximumUnder, which should really be in a library:

 maximumUnder :: Ord b => (a -> b) -> [a] -> a
 maximumUnder _ []     = error "maximumUnder: empty list"
 maximumUnder f (x:xs) = imax x (f x) xs where
   imax x _ []     = x
   imax x v (y:ys) = if v >= w then imax x v ys else imax y w ys where w = f y

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=: 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.

[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>();
        for(int subSize= 0;subSize<= array.size();subSize++){//loop through all possible subarray sizes including 0
            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
                for(long index:indices) {sum+= array.get(index); temp.add(array.get(index));}//sum it and save it
                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;
    }
}

[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] 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;

foreach 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);

[edit] 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]

[edit] 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

[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).