21
\$\begingroup\$

Define the "maximum sub-array" of a given array as "a (consecutive) sub-array that has the biggest sum". Note there's no "non-zero" requirement. Output that sum.

Give a description of your code if possible.

Sample input 1:

1 2 3 -4 -5 6 7 -8 9 10 -11 -12 -13 14

Sample output 1: 24

Description 1:
The biggest sum is yielded by cutting 6 7 -8 9 10 out and summing up.

Sample input 2: -1 -2 -3
Sample output 2: 0
Description 2: It's simple :) An empty subarray is the "biggest".

Requirement:

  • Don't read anything except stdin, and output should go to stdout.
  • Standard loopholes restrictions apply.

Ranking: The shortest program wins this .

\$\endgroup\$
  • 5
    \$\begingroup\$ Write a program that's as short as possible. I would recommend removing this requirement as it requires us to check every possible program in our language and make sure that we're using the shortest. \$\endgroup\$ – Okx Aug 12 '17 at 12:19
  • \$\begingroup\$ Requirement 2 is also unclear. Does it mean libraries? Custom libraries? Outsourcing the program? The latter is already prohibited by the standard loopholes. \$\endgroup\$ – Leaky Nun Aug 12 '17 at 12:22
  • 14
    \$\begingroup\$ Don't read anything except stdin, and don't write to anywhere except stdout. - Why? \$\endgroup\$ – Mr. Xcoder Aug 12 '17 at 12:54
  • 2
    \$\begingroup\$ Very similar, possibly a dupe. Also very similar. \$\endgroup\$ – xnor Aug 13 '17 at 0:28

25 Answers 25

10
\$\begingroup\$

Husk, 6 4 bytes

▲ṁ∫ṫ

Try it online!

      -- implicit input (list) xs  - eg. [-1,2,3]
   ṫ  -- get all tails of xs       -     [[-1,2,3],[2,3],[3],[]]
 ṁ∫   -- map & concat cumsum       -     [0,-1,1,4,0,2,5,0,3,0]
▲     -- get maximum               -     5
\$\endgroup\$
6
\$\begingroup\$

Python 3, 61 bytes

a=b=0
for x in eval(input()):a=max(x,a+x);b=max(a,b)
print(b)

Try it online!

Algorithm stolen from Wikipedia.

\$\endgroup\$
4
\$\begingroup\$

Pyth, 8 bytes

eS+0sM.:

Try it online!


How?

eS+0sM.:Q - Q is implicit, meaning input. Let's say it's [-1, -2, -3].

      .:  - All contiguous non-empty sublists. We have [[-1], [-2], [-3], [-1, -2], [-2, -3], [-1, -2, -3]].
    sM    - Get the sum of each sublist. [-1, -2, -3, -3, -5, -6]
  +0      - Append a 0 to the sum list. [0, -1, -2, -3, -3, -5, -6]
eS        - Maximum element. S gives us [-6, -5, -3, -3, -2, -1, 0], while e returns 0, the last element.
\$\endgroup\$
4
\$\begingroup\$

05AB1E, 4 bytes

Ό0M

Try it online!

-1 thanks to Adnan.

\$\endgroup\$
  • \$\begingroup\$ Same tip as with Okx's answer: ÎŒOM should work for 4 bytes. \$\endgroup\$ – Adnan Aug 12 '17 at 14:40
  • \$\begingroup\$ @Adnan Thanks I thought there was only a "1 and input" builtin...wait...does it? Shouldn't they be concatenated or something? \$\endgroup\$ – Erik the Outgolfer Aug 12 '17 at 14:42
  • \$\begingroup\$ Nope, M searches for the largest number in the flattened version of the stack. \$\endgroup\$ – Adnan Aug 12 '17 at 14:46
  • \$\begingroup\$ @Adnan ok...this is news to me lol \$\endgroup\$ – Erik the Outgolfer Aug 12 '17 at 14:47
3
\$\begingroup\$

Jelly, 6 bytes

ẆS€;0Ṁ

Try it online!

\$\endgroup\$
3
\$\begingroup\$

C++, 197 195 187 bytes

-10 bytes thanks to Zacharý

#include<vector>
#include<numeric>
int f(std::vector<int>v){int i=0,j,t,r=0;for(;i<v.size();++i)for(j=i;j<v.size();++j){t=std::accumulate(v.begin()+i,v.begin()+j,0);if(t>r)r=t;}return r;}
\$\endgroup\$
  • \$\begingroup\$ Can you remove the braces after the first for loop? \$\endgroup\$ – Zacharý Aug 12 '17 at 17:48
  • \$\begingroup\$ Also, why do you have l and h anyways? \$\endgroup\$ – Zacharý Aug 12 '17 at 21:33
  • \$\begingroup\$ @Zacharý l and h was for the start and end index of the sub array \$\endgroup\$ – HatsuPointerKun Aug 12 '17 at 21:38
3
\$\begingroup\$

R, 54 bytes

a=b=0;for(x in scan()){a=max(x,a+x);b=max(a,b)};cat(b)

Try it online!

Algorithm taken from: Maximum subarray problem

R, 65 bytes

y=seq(x<-scan());m=0;for(i in y)for(j in y)m=max(m,sum(x[i:j]));m

Try it online!

  • Read x from stdin.
  • Set y as index of x.
  • Iterate twice over all possible nonempty subsets.
  • Compare sum of a subset with m (initially m=0).
  • Store maximum value in m.
  • Print value of m.

R, 72 bytes

n=length(x<-scan());m=0;for(i in 1:n)for(j in i:n)m=max(m,sum(x[i:j]));m

Try it online!

  • Read x from stdin.
  • Do a full search over all possible nonempty subsets.
  • Compare sum of a subset with m (initially m=0).
  • Store maximum value in m.
  • Print value of m.

Other unsuccessful ideas

58 bytes

Reduce(max,lapply(lapply(seq(x<-scan()),tail,x=x),cumsum))

63 bytes

Reduce(max,lapply(seq(x<-scan()),function(i)cumsum(tail(x,i))))

72 bytes

m=matrix(x<-scan(),n<-length(x),n);max(apply(m*lower.tri(m,T),2,cumsum))
\$\endgroup\$
  • 1
    \$\begingroup\$ a=b=0 works too. Also, you need to handle printing of the output. When run as a full program (through source) this doesn't print anything. \$\endgroup\$ – JAD Aug 13 '17 at 9:14
  • \$\begingroup\$ @JarkoDubbeldam, I have added cat(b), but if sourced with echo=TRUE it is enough to call b for printout. \$\endgroup\$ – djhurio Aug 13 '17 at 12:11
  • \$\begingroup\$ I guess there isn't a clear definition on how full programs are run in R. There is rscript in commandline, and source in R itself. But usually flags needed when running a script are included in the bytecount. (I haven't personally managed to get rscript to work nicely with scan, but thats another thing. \$\endgroup\$ – JAD Aug 13 '17 at 13:19
  • \$\begingroup\$ You can use T=F instead of a=b=0 to save two bytes, because max will coerce b to numeric. \$\endgroup\$ – Giuseppe Oct 31 '17 at 17:25
3
\$\begingroup\$

Haskell, 28 bytes

maximum.scanl((max<*>).(+))0

Try it online!

\$\endgroup\$
  • \$\begingroup\$ won't the maximum always be the last element in the returned from scanl? so foldl((max<*>).(+))0 ?? \$\endgroup\$ – matthias Apr 4 '18 at 1:03
  • \$\begingroup\$ NVM i see my mistake! \$\endgroup\$ – matthias Apr 4 '18 at 1:09
  • \$\begingroup\$ @matthias If you see the edit history, you'll see that I made the sma mistake. :-) \$\endgroup\$ – H.PWiz Apr 4 '18 at 1:39
2
\$\begingroup\$

05AB1E, 4 bytes

-2 bytes thanks to Adnan

ÎŒOM

Try it online!

\$\endgroup\$
  • \$\begingroup\$ ÎŒOM should work for 4 bytes \$\endgroup\$ – Adnan Aug 12 '17 at 14:15
  • \$\begingroup\$ @Adnan Cool, thanks. \$\endgroup\$ – Okx Aug 12 '17 at 14:47
2
\$\begingroup\$

Mathematica, 24 bytes

Max[Tr/@Subsequences@#]&
\$\endgroup\$
2
\$\begingroup\$

Haskell, 41 33 bytes

import Data.List
g=maximum.concatMap(map sum.inits).tails
maximum.(scanl(+)0=<<).scanr(:)[]

Try it online! thanks to Laikoni

\$\endgroup\$
  • 1
    \$\begingroup\$ Anonymous functions are allowed as submission, so you can drop the g=. Instead of concatMap you can use =<< from the list monad: Try it online! (33 bytes). \$\endgroup\$ – Laikoni Oct 30 '17 at 11:03
1
\$\begingroup\$

Japt, 11 bytes

£ãY mxÃc rw

Try it online!

Explanation

£ãY mxÃc rw
m@ãY mx} c rw   // Ungolfed
m@     }        // Map the input array by the following function, with Y=index
  ãY            //   Get all subsections in input array length Y
     mx         //   Sum each subsection
         c rw   // Flatten and get max

Alternate method, 11 bytes

From @ETHproductions; based on Brute Forces' Husk answer.

£sY å+Ãc rw

Gets all tails of the input array and cumulatively sums each. Then flattens the array and gets the max.

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Nice, really nice. I didn't try to implement this challenge when I saw it earlier, but I did think of a different technique and expected it to come out around 15 bytes, so this is great. \$\endgroup\$ – ETHproductions Aug 13 '17 at 2:52
  • \$\begingroup\$ Looking at the Husk answer, there is another efficient way: £sY å+Ãc rw (also 11 bytes) \$\endgroup\$ – ETHproductions Aug 13 '17 at 2:56
  • \$\begingroup\$ @ETHproductions Pretty nice, I'll add that to this answer as an alternate method. Could that maybe be improved with some combination of reduce/concat, also like that Husk answer? \$\endgroup\$ – Justin Mariner Aug 13 '17 at 3:05
1
\$\begingroup\$

Ruby, 61 59 57 bytes

I just started learning Ruby, so this is what I came up with.

s=0
p [gets.split.map{|i|s=[j=i.to_i,s+j].max}.max,0].max

I first saw this algorithm at the Finnish version of this unfinished book. It is very well explained at the page 23.

Try it online!

\$\endgroup\$
1
\$\begingroup\$

JavaScript, 58 bytes

m=Math.max;x=y=>eval("a=b=0;for(k of y)b=m(a=m(a+k,k),b)")

Golfed JS implementation of Kadane's algorithm. Made as short as possible. Open to constructive suggestions!

What I learnt from this post: return value of eval - when its last statment is a for loop - is basically the last value present inside the loop. Cool!

EDIT: saved four bytes thanks to Justin's and Hermann's suggestions.

\$\endgroup\$
  • \$\begingroup\$ You can avoid the return by replacing {...;return b;} with eval("...;b") since eval returns the last statement. \$\endgroup\$ – Justin Mariner Aug 13 '17 at 19:13
  • \$\begingroup\$ @JustinMariner thanks! am always learning something new here :) \$\endgroup\$ – Gaurang Tandon Aug 14 '17 at 9:25
  • \$\begingroup\$ You can remove two more bytes by removing ;b, since it's returned from the for loop \$\endgroup\$ – Herman L Oct 29 '17 at 14:36
  • \$\begingroup\$ @HermanLauenstein Oh, wow, thanks, that's useful! \$\endgroup\$ – Gaurang Tandon Oct 29 '17 at 15:54
0
\$\begingroup\$

Gaia, 6 bytes

0+ḋΣ¦⌉

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Python 2, 52 51 bytes

f=lambda l:len(l)and max(sum(l),f(l[1:]),f(l[:-1]))

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ This seems to conflict (the otherwise unnecessary) requirement Don't read anything except stdin, and don't write to anywhere except stdout. \$\endgroup\$ – Mr. Xcoder Aug 12 '17 at 13:29
0
\$\begingroup\$

Common Lisp, 73 bytes

(lambda(a &aux(h 0)(s 0))(dolist(x a s)(setf h(max x(+ h x))s(max s h))))

Try it online!

\$\endgroup\$
0
\$\begingroup\$

k, 14 bytes

|/,/+\'(1_)\0,

Try it online!

            0, /prepend a zero (in case we're given all negatives)
       (1_)\   /repeatedly remove the first element, saving each result
    +\'        /cumulative sum over each result, saving each result
  ,/           /flatten (fold concat)
|/             /maximum (fold max)
\$\endgroup\$
0
\$\begingroup\$

APL, 31 29 27 bytes

⌈/∊∘.{+/W[X/⍨⍺≤X←⍳⍵]}⍨⍳⍴W←⎕

Try it online! (modified so it will run on TryAPL)

How?

  • ∊∘.{+/W[X/⍨⍺≤X←⍳⍵]}⍨⍳⍴W←⎕ Generate sums of subvectors
  • ⌈/ Maximum
\$\endgroup\$
0
\$\begingroup\$

CJam, 24 bytes

q~:A,{)Aew{:+}%}%e_0+:e>

Function that takes array of numbers as input.

Try it Online

q~:A   e# Store array in 'A' variable
,{)Aew e# Get every possible sub-array of the array
{:+}%  e# Sum every sub array
}e_    e# flatten array of sums
0+     e# Add zero to the array
:e>    e# Return max value in array
\$\endgroup\$
0
\$\begingroup\$

MY, 11 bytes

⎕𝟚35ǵ'ƒ⇹(⍐↵

Try it online! MY is on TIO now! Woohoo!

How?

  • = evaluated input
  • 𝟚 = subvectors
  • 35ǵ' = chr(0x53) (Σ, sum)
  • ƒ = string as a MY function
  • = map
  • ( = apply
  • = maximum
  • = output with a newline.

Sum was fixed (0 on empty arrays) in order for this to work. Product was also fixed.

\$\endgroup\$
0
\$\begingroup\$

J, 12 bytes

[:>./@,+/\\.

Similar to zgrep's K solution: the scan sum of all suffixes (produces a matrix), raze, take max

Try it online!

NOTE

for not too many more bytes, you can get an efficient solution (19 bytes golfed):

[: >./ [: ({: - <./)\ +/\
\$\endgroup\$
0
\$\begingroup\$

Axiom, 127 bytes

f(a:List INT):Complex INT==(n:=#a;n=0=>%i;r:=a.1;for i in 1..n repeat for j in i..n repeat(b:=reduce(+,a(i..j));b>r=>(r:=b));r)

This would be O(#a^3) Algo; I copy it from the C++ one... results

(3) -> f([1,2,3,-4,-5,6,7,-8,9,10,-11,-12,-13,14])
   (3)  24
                                                    Type: Complex Integer
(4) -> f([])
   (4)  %i
                                                    Type: Complex Integer
(5) -> f([-1,-2,3])
   (5)  3
                                                    Type: Complex Integer
\$\endgroup\$
0
\$\begingroup\$

Scala, 105 bytes

val l=readLine.split(" ").map(_.toInt);print({for{b<-l.indices;a<-0 to b+2}yield l.slice(a,b+1).sum}.max)

I didn't find any better way to generate the sublists arrays.

\$\endgroup\$
0
\$\begingroup\$

Java 8, 242 bytes

import java.util.*;v->{List a=new Stack();for(String x:new Scanner(System.in).nextLine().split(" "))a.add(new Long(x));int r=0,l=a.size(),i=l,j,k,s;for(;i-->0;)for(j=l;--j>1;r=s>r?s:r)for(s=0,k=i;k<j;)s+=(long)a.get(k++);System.out.print(r);}

Try it here.

106 bytes without using STDIN/STDOUT requirement.. >.>

a->{int r=0,l=a.length,i=l,j,k,s;for(;i-->0;)for(j=l;--j>1;r=s>r?s:r)for(s=0,k=i;k<j;s+=a[k++]);return r;}

Try it here.

Explanation:

import java.util.*;      // Required import for List, Stack and Scanner

v->{                     // Method with empty unused parameter and no return-type
  List a=new Stack();    //  Create a List
  for(String x:new Scanner(System.in).nextLine().split(" "))
                         //  Loop (1) over the STDIN split by spaces as Strings
    a.add(new Long(x));  //   Add the String converted to a number to the List
                         //  End of loop (1) (implicit / single-line body)
  int r=0,               //  Result-integer
      l=a.size(),        //  Size of the List
      i=l,j,k,           //  Index-integers
      s;                 //  Temp sum-integer
  for(;i-->0;)           //  Loop (2) from `l` down to 0 (inclusive)
    for(j=l;--j>1;       //   Inner loop (3) from `l-1` down to 1 (inclusive)
        r=               //     After every iteration: change `r` to:
          s>r?           //      If the temp-sum is larger than the current `r`:
           s             //       Set `r` to the temp-sum
          :              //      Else:
           r)            //       Leave `r` the same
      for(s=0,           //    Reset the temp-sum to 0
          k=i;k<j;)      //    Inner loop (4) from `i` to `j` (exclusive)
        s+=(long)a.get(k++);
                         //     Add the number at index `k` in the List to this temp-sum
                         //    End of inner loop (4) (implicit / single-line body)
                         //   End of inner loop (3) (implicit / single-line body)
                         //  End of loop (2) (implicit / single-line body)
  System.out.print(r);   //  Print the result to STDOUT
}                        // End of method
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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