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]);
  • 2
    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
  • 2
    Wouldn't it give 131? 20+9+76+5+4=114 and 19+80+32=131 – Joanis Dec 31 '11 at 21:17
  • 3
    possible duplicate of Find largest sum of subsequence – Peter Taylor Jan 1 '12 at 2:44
  • 1
    @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
  • 1
    @userunknown I stand corrected. – arrdem Jan 2 '12 at 19:57

17 Answers 17

up vote 1 down vote accepted

Perl: 56 53 characters

Thanks to Ilmari Karonen

push@s,$_>0?$_+pop@s:0for@ARGV;say+(sort{$b-$a}@s)[0]
  • 1
    Can be golfed down to 53: push@s,$_>0?$_+pop@s:0for@ARGV;say+(sort{$b-$a}@s)[0] – 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, 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('-')))
  • 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
  • 1
    @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)[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! – Shaggy Jul 31 at 17:21
  • @Shaggy Don't worry, this helps me get better. Thanks – Luis felipe De jesus Munoz Jul 31 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 (xs.tail, sofar + xs.head) 
}
sumup (List (12, 2, 35, -1, 20, 9, 76, 5, 4, -3, 4, -5, 19, 80, 32, -1))

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

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!

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.