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

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!

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

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

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

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!

Answer 8

Perl: 56 53 characters

Thanks to Ilmari Karonen

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

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

Perl6 with MoarVM, 53 chars

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

Answer 14

PHP, 56 bytes

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

Run with -nr.

Answer 15

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 16

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.

Answer 17

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

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

Try it online!