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

• This lacks an objective winning criterion. Also, as the rules are, I could just print 179 and have a valid solution. – cemper93 Dec 31 '11 at 21:06
• Wouldn't it give 131? 20+9+76+5+4=114 and 19+80+32=131 – Joanis Dec 31 '11 at 21:17
• possible duplicate of Find largest sum of subsequence – Peter Taylor Jan 1 '12 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". – cemper93 Jan 2 '12 at 13:58
• @userunknown I stand corrected. – arrdem Jan 2 '12 at 19:57

## Perl: 56 53 characters

Thanks to Ilmari Karonen

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

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

## 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? – FUZxxl Feb 22 '15 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. – jimmy23013 Feb 23 '15 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) – Martin Ender Feb 23 '15 at 7:34
• But that might be because I'm not bothered to post a longer answer in APL... Still 27% shorter, though. – jimmy23013 Feb 23 '15 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). – Dillon Cower Jan 3 '12 at 7:32
• @DC: Awesome improvement! Thank you. I especially like multiplying by the result of the conditional. – Steven Rumbalski Jan 4 '12 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. – arrdem Jan 2 '12 at 4:52
• @rmckenzie: raw_input was renamed input in Python 3. The Python 2 meaning of input was dropped. – Steven Rumbalski Jan 2 '12 at 19:10
• I knew I was missing something.... – arrdem Jan 2 '12 at 19:57

## Perl, 45 chars

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


(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! – Shaggy Jul 31 '18 at 17:21
• @Shaggy Don't worry, this helps me get better. Thanks – Luis felipe De jesus Munoz Jul 31 '18 at 17:25

## 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,4],[2,4,-5],[2,4,-5,7],,[4,-5],[4,-5,7],[-5],[-5,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,4],,] → [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. ## Perl 5 +-pa -MList::Util+(max), 28 bytes $_=max map/-/?$-=0:$-+=\$_,@F


Try it online!