Find largest sum of subsequence 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 &lt;stdio.h&gt;
#include &lt;assert.h&gt;


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

unsigned get_random()
{
  m_z = 36969 * (m_z &amp; 65535) + (m_z &gt;&gt; 16);
  m_w = 18000 * (m_w &amp; 65535) + (m_w &gt;&gt; 16);
  return (m_z &lt;&lt; 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() &lt;&lt; 8 &gt;&gt; 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.
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().