# 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);
m_z = atoi(argv);

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

i = atoi(argv);
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 <stdlib.h> for atoi(). Jul 3, 2011 at 13:46
• My own c solution take 4 seconds for last test case, very interested about your solution. Jul 3, 2011 at 23:16
• Make sure you write first to a file and then read from file, and not use pipes. Jul 4, 2011 at 8:42
• I guess there is an error in your generator, line 25,while (i--); shouldn't end in an semicolon, should it? Jan 2, 2012 at 5:37
• assert(argc==3) :-) That's what I call a user friendly program! :-) Feb 23, 2015 at 11:45

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

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. ## Haskell (88 64) Implementing Kadane's algorithm. main=interact$show.maximum.scanr(\x->max x.(x+))0.map read.lines


Python - 114 chars

import sys
l=range(len(s)+1)
printmax(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. Jul 3, 2011 at 6:57

Python, using dynamic programming - 92 chars

import sys
f=h=0
for x in s:h=max(0,h+x);f=max(f,h)
print f


## 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\. yu 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 , ([ >. +)/\. y0 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.

## 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;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 Sep 13, 2012 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