The group of sequential positive numbers with the highest sum?

Question

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]);

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

Answer 1

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 (⍵₁ , ⍵₁ ∧ ⍵₂ , ⍵₁ ∧ ⍵₂ ∧ ⍵₃ , ...). 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!

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

Answer 2

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

• jimmy23013: K is an APL variant. You have won by only 4 bytes.
• Martin Ender: @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)
• jimmy23013: But that might be because I'm not bothered to post a longer answer in APL... Still 27% shorter, though.

Answer 3

Python 3, (削除) 93 (削除ここまで) (削除) 80 (削除ここまで) (削除) 79 (削除ここまで) 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('-')))

• Dillon Cower: 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).
• Steven Rumbalski: @DC: Awesome improvement! Thank you. I especially like multiplying by the result of the conditional.

Answer 4

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

• arrdem: 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.
• Steven Rumbalski: @rmckenzie: raw_input was renamed input in Python 3. The Python 2 meaning of input was dropped.
• arrdem: I knew I was missing something....

Answer 5

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

Answer 6

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.

Answer 7

Japt -hx, (削除) 9 (削除ここまで) 6 bytes

-3 bytes from @Shaggy

ô<0 ñx

Try it online!

• Shaggy: 6 bytes. Apologies for all the comments; trying to do too many things at once!
• Luis felipe De jesus Munoz: @Shaggy Don't worry, this helps me get better. Thanks

Answer 8

Perl: (削除) 56 (削除ここまで) 53 characters

Thanks to Ilmari Karonen

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

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

Answer 9

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

Answer 10

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}

Answer 11

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 (xs.tail, sofar + xs.head) 
}
sumup (List (12, 2, 35, -1, 20, 9, 76, 5, 4, -3, 4, -5, 19, 80, 32, -1))

Answer 12

05AB1E, 8 bytes

Œʒß0›}Oà

Try it online.

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

Answer 13

Ruby, 34 bytes

->a{a.chunk{_1>0}.map{_2.sum}.max}

Attempt This Online!

Answer 14

Perl6 with MoarVM, 53 chars

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

Answer 15

PHP, 56 bytes

while(~$n=$argv[++$i])$n<0?$k++:$r[$k]+=$n;echo max($r);

Run with -nr.

Answer 16

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
}

Answer 17

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.

• ceilingcat: 66 bytes

Answer 18

Perl 5 +-pa -MList::Util+(max), 28 bytes

$_=max map/-/?$-=0:$-+=$_,@F

Try it online!