# The group of sequential positive numbers with the highest sum?

Given the following list of numbers, find the group of sequential positive numbers with the highest sum.

Example input:

12 2 35 -1 20 9 76 5 4 -3 4 -5 19 80 32 -1


Example output:

131


The most succinct code wins.

My approach via Perl is 87 chars (with input as command-line args):

print((sort { $b <=>$a } do { push @s, $_ > 0 ? pop(@s) +$_ : 0 for @ARGV; @s })[0]);

• This lacks an objective winning criterion. Also, as the rules are, I could just print 179 and have a valid solution. Dec 31, 2011 at 21:06
• Wouldn't it give 131? 20+9+76+5+4=114 and 19+80+32=131 Dec 31, 2011 at 21:17
• possible duplicate of Find largest sum of subsequence Jan 1, 2012 at 2:44
• @Al Newkirk: You should specify which solution will be the winner. If this shall be the solution with the least characters (standard code-golf), please add a code golf tag. Also, don't say "use the following input", but specify something like "the input will be on standard input, and use the following input to test your submission". Jan 2, 2012 at 13:58
• @userunknown I stand corrected. Jan 2, 2012 at 19:57

## APL, 35 characters

i←⎕⋄⌈/{{+/⍵/⍨∧\⍵>0}⍵↓i}¨0,(i≤0)/⍳⍴i


I used Dyalog APL for this. ⎕IO should be set to its default of 1.

Example (note that high-minus, ¯, must be used instead of regular minus):

      i←⎕⋄⌈/{{+/⍵/⍨∧\⍵>0}⍵↓i}¨0,(i≤0)/⍳⍴i
⎕:
12 2 35 ¯1 20 9 76 5 4 ¯3 4 ¯5 19 80 32 ¯1
131


Explanation (roughly right-to-left for each expression):

• First, we get (and evaluate) the input: i←⎕. (⋄ separates expressions in a single statement.)
• (i≤0)/⍳⍴i is an idiom to get the list of the locations of elements of i that are ≤0.
• i≤0 returns a vector of binary values, where each element is 1 if the corresponding element in i is ≤0, and 0 otherwise.
• ⍳⍴i returns a list of integers, from 1 to the shape (length) of i.
• The replication function, /, replicates each value in its right argument n times, where n is the corresponding element in its left argument. Because we have a binary list, this just includes or excludes elements (replicating them 0 or 1 times).
• We tack a 0 on the beginning, using the concatenation operator (,).
• Now, using the example input, we have the vector 0 4 10 12 16. We use the each operator, ¨, to map a function (its left operand) to each element of this list.
• The function is a direct function (basically, an anonymous function), and its definition is surrounded with curly braces. Its right argument is represented by the omega symbol, ⍵.
• For each element of our vector:
• The outermost function, {{ ... }⍵↓i}, returns the vector i, with ⍵ elements dropped (↓) from the beginning. This is then fed to...
• The innermost function, {+/⍵/⍨∧\⍵>0}, in slightly less golfed form is {+/(∧\⍵>0)/⍵}.
• (∧\⍵>0)/⍵ is similar to the aforementioned idiom. First we generate a list of elements in ⍵ that are above 0. Then, we use the scan operator, \, along with the bitwise-AND function, ∧, to return the list (⍵1 , ⍵1 ∧ ⍵2 , ⍵1 ∧ ⍵2 ∧ ⍵3 , ...). In other words, this list consists of 1's up until the first non-positive element, where it is then all 0's. We use replication as before.
• We now use the reduction operator, (also) represented by /, along with the addition function, +, to fold all positive elements in the current list, up to (but not including) the first non-positive one.
• Lastly, we fold again, this time with the maximum function, ⌈.

Here are snapshots showing the results of some stages:

      i≤0
0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1

⍳⍴i
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

0,(i≤0)/⍳⍴i
0 4 10 12 16

{⍵↓i}¨0,(i≤0)/⍳⍴i
12 2 35 ¯1 20 9 76 5 4 ¯3 4 ¯5 19 80 32 ¯1  20 9 76 5 4 ¯3 4 ¯5 19 80 32 ¯1  4 ¯5 19 80 32 ¯1  19 80 32 ¯1

{{(∧\⍵>0)}⍵↓i}¨0,(i≤0)/⍳⍴i
1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0  1 1 1 1 1 0 0 0 0 0 0 0  1 0 0 0 0 0  1 1 1 0

{{(∧\⍵>0)/⍵}⍵↓i}¨0,(i≤0)/⍳⍴i
12 2 35  20 9 76 5 4  4  19 80 32

{{+/(∧\⍵>0)/⍵}⍵↓i}¨0,(i≤0)/⍳⍴i
49 114 4 131 0


Hopefully some of this makes a bit of sense!

• How about ⌈/{{+/⍵/⍨∧\⍵>0}⍵↓i}¨0,(i≤0)/⍳⍴i←⎕ for a size reduction by two characters? Feb 22, 2015 at 20:55

# CJam, 16 byte

This answer is not eligible for the green checkmark, as CJam is much newer than this challenge (and this answer relies on even newer features). However, I thought this was a really neat approach (and hey, I'm beating APL by quite a margin!), so I wanted to post it anyway.

l~]0fe>0a%::+$W=  Test it here. ## Explanation l~] "Read input, eval, wrap in array."; 0fe> "Map max(0,x) onto the list, turning all non-positive numbers into 0."; 0a% "Split the list on zeroes - i.e. split into positive subarrays."; ::+ "Map a fold of + onto the array - i.e. compute the sum of each subarray.";$W= "Sort and get the last element - i.e. the maximum.";

• K is an APL variant. You have won by only 4 bytes. Feb 23, 2015 at 7:08
• @user23013 I know it is... Doesn't mean I haven't beaten one member of the APL family by a considerable margin ;) (also even those four bytes are 20% which isn't exactly close) Feb 23, 2015 at 7:34
• But that might be because I'm not bothered to post a longer answer in APL... Still 27% shorter, though. Feb 23, 2015 at 7:41

## Python 3, 938079 71 chars

a=b=0
for i in map(int,input().split()):b+=i;b*=i>0;a=max(a,b)
print(a)


Thanks to D C for pointing out how to save 8(!) characters from this:

a=b=0
for i in map(int,input().split()):b+=i;a=[a,b][b>a];b=[0,b][i>0]
print(a)


Saved one character by indexing by true/false rather than if statements.

It is much less readable than the equivalent 80 char version:

a=b=0
for i in map(int,input().split()):
b+=i
if b>a:a=b
if i<=0:b=0
print(a)


The 93 character version converted to int later in the game:

print(max(sum(map(int,s.split()[1:]))for s in('-1 '+input().replace(' 0','-1')).split('-')))

• You can shave 8 characters off by replacing b+=i;a=[a,b][b>a];b=[0,b][i>0] with b+=i;b*=i>0;a=max(a,b). Jan 3, 2012 at 7:32
• @DC: Awesome improvement! Thank you. I especially like multiplying by the result of the conditional. Jan 4, 2012 at 19:54

## Python 3 (92)

Reads the list of numbers from stdin.

m,s=0,[]
for x in map(int,input().split()):
if x<0:s+=[m];m=0
else:m+=x
print(max([m]+s))

• You are missing a few chars and throwing an error as a result, 1input() has to be be raw_input(). Also, 0 is not considered positive so instead of x<0, you could just have x. Otherwise this seems to have hit Kolmogorov for python. Jan 2, 2012 at 4:52
• @rmckenzie: raw_input was renamed input in Python 3. The Python 2 meaning of input was dropped. Jan 2, 2012 at 19:10
• I knew I was missing something.... Jan 2, 2012 at 19:57

## Perl, 45 chars

say+(sort{$b-$a}map$p=$_>0?$_+=$p:0,@ARGV)[0]


(Uses say, so needs to be run with perl 5.10+ and the -M5.010 (or -E) switch.)

# APL, 22 20

⌈/∊(+\×{∧\0<⍵})¨,⍨\⎕


To test it online:

{⌈/∊(+\×{∧\0<⍵})¨,⍨\⍵}


Try it here.

### Explanation

{                ,⍨\⍵}    ⍝ Get a list of reversed prefixes.
{  0<⍵}           ⍝ Check if each item is >0.
{∧\0<⍵}           ⍝ Check if each prefix is all >0.
+\                   ⍝ Sum of each prefix.
(+\×{∧\0<⍵})          ⍝ Sum * all>0 for each prefix.
{   (+\×{∧\0<⍵})¨,⍨\⍵}    ⍝ Apply that to each reversed prefixes (So the prefixes of
⍝   reversed prefixes are reversed suffixes of prefixes of
⍝   the original string).
{  ∊(+\×{∧\0<⍵})¨,⍨\⍵}    ⍝ Flatten the array.
{⌈/∊(+\×{∧\0<⍵})¨,⍨\⍵}    ⍝ Find the maximum.


# Japt-hx, 9 6 bytes

-3 bytes from @Shaggy

ô<0 ñx


Try it online!

• 6 bytes. Apologies for all the comments; trying to do too many things at once! Jul 31, 2018 at 17:21
• @Shaggy Don't worry, this helps me get better. Thanks Jul 31, 2018 at 17:25

## Perl: 56 53 characters

Thanks to Ilmari Karonen

push@s,$_>0?$_+pop@s:0for@ARGV;say+(sort{$b-$a}@s)[0]

• Can be golfed down to 53: push@s,$_>0?$_+pop@s:0for@ARGV;say+(sort{$b-$a}@s)[0] Jan 4, 2012 at 16:16
• @IlmariKaronen: Yes, nice use of $b-$a in sort.
– Toto
Jan 4, 2012 at 18:30

## Racket, 108 chars

Once golfed, it gives 133 chars with intermediary "f", or 108 if you use "g" directly.

(define f
(λ (l)
(g l 0 0)))

(define g
(λ (l M c)
(cond
((null? l) (max M c))
((> 0 (car l)) (g (cdr l) (max M c) 0))
(else
(g (cdr l) M (+ (car l) c))))))

(f '(12 2 35 -1 20 9 76 5 4 -3 4 -5 19 80 32 -1)) ;-> 131


Where "l" is the list of values, "M" is the maximum sum yet encountered, and "c" is the current sum.

Golfed:

(define f(λ(l)(g l 0 0)))(define g(λ(l M c)(cond((null? l)(max M c))((> 0(car l))(g(cdr l)(max M c)0))(else(g(cdr l)M(+(car l)c))))))


# K, 20

{max@+/'1_'(&x<0)_x}


Finds the indices where x<0, cuts the list at those indices, drops the negative numbers, sums and finds the maximum.

k){max@+/'1_'(&x<0)_x}12 2 35 -1 20 9 76 5 4 -3 4 -5 19 80 32 -1
131


Equivalent in q:

{max sum each 1_'(where x<0)_x}


### Scala: 102 chars

def s(x:Seq[Int],y:Int=0):Int={
if(x==Nil)y else
if(x(0)<0)math.max(y,s(x.tail))else
s(x.tail,y+x(0))}

val data = List (12, 2, 35, -1, 20, 9, 76, 5, 4, -3, 4, -5, 19, 80, 32, -1)
s(data)


ungolfed:

def sumup (xs: Seq[Int], sofar: Int=0): Int = {
if (xs.isEmpty) sofar else
if (xs.head < 0) sofar + sumup (xs.tail) else
}
sumup (List (12, 2, 35, -1, 20, 9, 76, 5, 4, -3, 4, -5, 19, 80, 32, -1))


# 05AB1E, 8 bytes

Œʒß0›}Oà


Explanation:

Œ           # Get all sub-lists of the input-list
#  i.e. [2,4,-5,7]
#    → [[2],[2,4],[2,4,-5],[2,4,-5,7],[4],[4,-5],[4,-5,7],[-5],[-5,7],[7]]
ʒ   }      # Filter this list of lists by:
ß         #  Take the smallest value of the inner list
#   i.e. [4,-5,7] → -5
0›       #  Check if it's larger than 0
#   i.e. -5>0 → 0 (falsey)
O          # Take the sum of each remaining item
#  i.e. [[2],[2,4],[4],[7]] → [2,6,4,7]
à         # And take the maximum of the sums
#  i.e. [2,6,4,7] → 7


# Perl6 with MoarVM, 53 chars

@a[$_ <0??++$i-$i!!$i||++$i]+=$_ for lines;@a.max.say


# PHP, 56 bytes

while(~$n=$argv[++$i])$n<0?$k++:$r[$k]+=$n;echo max($r);  Run with -nr. # Java 8, 72 62 bytes l->{int c=0,m=0;for(int i:l){c=i>0?c+i:0;m=m<c?c:m;}return m;}  Try it online here. Ungolfed: l -> { // lambda taking a List as argument and returning an int int c = 0, m = 0; // two sums: c is the sum of the current run of positive integers; m is the maximum sum found so far for(int i : l) { // for each element in the list: c = i > 0 ? c + i : 0; // if the number is positive, extend the current run by adding it to the sum; otherwise reset the sum to zero m = m < c ? c : m; // if the maximum recorded so far is smaller than the current sum, record the current sum as the new maximum } return m; // return the maximum }  # C (gcc/tcc), 69 bytes c,m;f(int*a,int*b){c=m=0;for(;a<b;++a){c=*a>0?c+*a:0;m=m<c?c:m;}a=m;}  Port of my Java answer. Try it online here. • 66 bytes Aug 2, 2018 at 2:45 ## Perl 5 +-pa -MList::Util+(max), 28 bytes $_=max map/-/?$-=0:$-+=\$_,@F


Try it online!