Find largest sum of subsequence

Question

Given a sequence of integers find the largest sum of a subsequence (integers on consecutive positions) of the sequence. The subsequence can be empty (in which case the sum is 0).

Input is read from standard input, one integer per line. The largest sum must be written to standard output.

I wrote a small generator for you:

#include <stdio.h>
#include <assert.h>


/* From http://en.wikipedia.org/wiki/Random_number_generation */
unsigned m_w;
unsigned m_z;

unsigned get_random()
{
  m_z = 36969 * (m_z & 65535) + (m_z >> 16);
  m_w = 18000 * (m_w & 65535) + (m_w >> 16);
  return (m_z << 16) + m_w;  /* 32-bit result */
}

int main(int argc, char **argv)
{
  int i;

  assert(argc == 3);
  m_w = atoi(argv[1]);
  m_z = atoi(argv[2]);

  i = 10;
  while (i--);
    get_random();

  i = atoi(argv[2]);
  while (i--)
    printf("%d\n", (int) get_random() << 8 >> 22);

  return 0;
}

Examples:

$ printf "1\n2\n-1\n4\n" | ./sum
6
$ printf "0\n-2\n-3\n" | ./sum
0

$ ./a.out 1 1 | ./sum
387
$ ./a.out 1 10 | ./sum
571
$ ./a.out 1 100 | ./sum
5867
$ ./a.out 1 1000 | ./sum
7531
$ ./a.out 1 10000 | ./sum
27268
$ ./a.out 1 100000 | ./sum
101332
$ ./a.out 1 1000000 | ./sum
187480
$ ./a.out 1 10000000 | ./sum
666307

• ./sum is my solution
• ./a.out is the generator

Your solution must run in reasonable time for all tests above (mine runs in 1.2s on the last test case).

Shortest code wins.

Edit: Please provide an example run on one of the tests above.

Answer 1

Python, 91 84 64 chars

s=m=0
try:
 while 1:s=max(s+input(),0);m=max(m,s)
except:print m

Takes about 14 12 72 seconds on the last test case. Edit: using algorithm Paul R found. Edit: nixed the import, using input().

Answer 2

C, 100 characters

main(){char s[80];int i,m=0,n=0;while(gets(s)){i=atoi(s);n=n+i>0?n+i:0;m=m>n?m:n;}printf("%d\n",m);}

Run time = 1.14 s for final test case (10000000) on 2.67 GHz Core i7 with ICC 11.1 (previously: 1.44 s with gcc 4.2.1).

Note: The algorithm used for the above solution comes from Programming Pearls by Jon Bentley. Apparently this algorithm is known as Kadane's Algorithm.

Answer 3

Ruby, 53 characters

p$<.inject(-1.0/s=0){|a,b|[s=[0,s+b.to_i].max,a].max}

Takes about 28 seconds for the last testcase here.

Answer 4

Haskell (88 64)

Implementing Kadane's algorithm.

main=interact$show.maximum.scanr(\x->max x.(x+))0.map read.lines

Answer 5

Python - 114 chars

import sys
s=map(int,sys.stdin.readlines())
l=range(len(s)+1)
print`max(sum(s[i:j])for i in l[:-1]for j in l[i:])`

It surely isn't as fast as required, but it works allright.

Answer 6

Python, using dynamic programming - 92 chars

import sys
s=map(int,sys.stdin.readlines())
f=h=0
for x in s:h=max(0,h+x);f=max(f,h)
print f

Answer 7

J (34 33 characters)

This solution implements a variant of Kadane's algorithm and is reasonable fast.

echo>./0,([>.+)/\.0".];._2(1!:1)3

Here is an explanation:

• u/ y – The verb u inserted between items of y. E.g., +/ 1 2 3 4 is like 1 + 2 + 3 + 4. Notice that all verbs in J are right-associated, that is, -/ 1 2 3 4 is like 1 - (2 - (3 - 4)) and computes the alternating sum of 1 2 3 4.
• x >. y – the maximum of x and y.
• x ([ >. +) y – The maximum of x and x + y. [ >. + is a verb in tacit notation and evaluates to the same as x >. x + y.
• ([ >. +)/ y – the non-empty prefix of y with the largest sum.
• u\. y – u applied to all suffixes of y. Notice that special code handles the common case u/\. y such that this runs in linear instead of quadratic time.
• ([ >. +)/\. y – A vector denoting the largest non-empty subarray that starts at each position of y.
• 0 , ([ >. +)/\. y – 0 preprended to the previous result as 0 is the length of an empty subarray of y.
• >./ 0 , ([ >. +)/\. y – The largest subarray of y.
• 0 ". ];._2 (1!:1) 3 – Standard input marshalled into a vector of numbers.
• >./ 0 , ([ >. +)/\. 0 ". ];._2 (1!:1) 3 – The largest subarray in standard input.

Answer 8

Ruby, 68 chars

m=-2**31;n=0;$<.lines.map{|x|n+=x.to_i;n=0 if n<0;m=n if n>m};puts m

Also a bit slow, but completes the 1-10000000 tests in a bit over half minute, most of the time spent in the last test...

Indented version:

m=-2**31
n=0
$<.lines.map {|x|
  n+=x.to_i
  n=0 if n<0
  m=n if n>m
}
puts m

Answer 9

C++, 192 chars

#include <iostream>
#include <string>
#include <stdlib.h>
#define S std::
main(){long a=0,m=0,M=0;char s[9];while(S cin.getline(s,9)){a+=atoi(s);if(m>a)m=a;if(M<a-m)M=a-m;}S cout<<M<<S endl;}

Works reasonably fast on my laptop (4 seconds for the last test).

Answer 10

{if((r+$1)>0)
   r=r+$1 
 else r=0; 
 if(m<r) 
   m=r;
}
END{print m}

awk Code (66), very slow, 8+ seconds for last test case

dwang@dwang-ws ~/Playground/lss $ time ./random 1 10000000 | awk -f lss.awk
666307

real    0m6.705s
user    0m8.671s
sys 0m0.052s