# 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 <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.

-
 You need `#include ` for `atoi()`. – Paul R Jul 3 '11 at 13:46 My own c solution take 4 seconds for last test case, very interested about your solution. – Dongshengcn Jul 3 '11 at 23:16 Make sure you write first to a file and then read from file, and not use pipes. – Alexandru Jul 4 '11 at 8:42 I guess there is an error in your generator, line 25,`while (i--);` shouldn't end in an semicolon, should it? – user unknown Jan 2 '12 at 5:37

## 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.

-

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()`.

-

## 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.

-
+1 for Programming Pearls. What a book. – BlackJack Jul 9 '11 at 22:38

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.

-
 This is O(N^2) which certainly doesn't meet requirements of the challenge. – Alexandru Jul 3 '11 at 6:57

## 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)

-

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
``````
-

## 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
``````
-

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

-
 `cstdlib` not `stdlib.h` – oldrinb Sep 13 '12 at 4:21
``````{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
``````
-