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

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 2

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 3

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 4

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 5

Haskell (88)

import List
main=interact$show.maximum.map sum.(>>=init.tails).tail.inits.map read.lines

(Brute force; does certainly not meets the requirements)

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

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 8

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 9

{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