# Maximum sub-array

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 .

• 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.
– Okx
Commented Aug 12, 2017 at 12:19
• Requirement 2 is also unclear. Does it mean libraries? Custom libraries? Outsourcing the program? The latter is already prohibited by the standard loopholes. Commented Aug 12, 2017 at 12:22
• Don't read anything except stdin, and don't write to anywhere except stdout. - Why? Commented Aug 12, 2017 at 12:54
• Very similar, possibly a dupe. Also very similar.
– xnor
Commented Aug 13, 2017 at 0:28

# 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
• another 4 byter Commented Nov 10, 2020 at 11:50

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

ẆS€;0Ṁ

Try it online!

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.

# 05AB1E, 4 bytes

ÎŒ0M

Try it online!

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

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

Try it online!

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

## C++, 197195 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;}
• Can you remove the braces after the first for loop? Commented Aug 12, 2017 at 17:48
• Also, why do you have l and h anyways? Commented Aug 12, 2017 at 21:33
• @Zacharý l and h was for the start and end index of the sub array Commented Aug 12, 2017 at 21:38

# 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!

• 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!

• 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))
• 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.
Commented Aug 13, 2017 at 9:14
• @JarkoDubbeldam, I have added cat(b), but if sourced with echo=TRUE it is enough to call b for printout. Commented Aug 13, 2017 at 12:11
• 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.
Commented Aug 13, 2017 at 13:19
• You can use T=F instead of a=b=0 to save two bytes, because max will coerce b to numeric. Commented Oct 31, 2017 at 17:25

# 05AB1E, 4 bytes

ÎŒOM

Try it online!

• ÎŒOM should work for 4 bytes Commented Aug 12, 2017 at 14:15
– Okx
Commented Aug 12, 2017 at 14:47

# Mathematica, 24 bytes

Max[Tr/@Subsequences@#]&

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

Try it online! thanks to Laikoni

• 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). Commented Oct 30, 2017 at 11:03

0+ḋΣ¦⌉

Try it online!

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

# 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!

• 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. Commented Aug 13, 2017 at 2:52
• Looking at the Husk answer, there is another efficient way: £sY å+Ãc rw (also 11 bytes) Commented Aug 13, 2017 at 2:56
• @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? Commented Aug 13, 2017 at 3:05

# Ruby, 6159 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!

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

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

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

[: >./ [: ({: - <./)\ +/\

# Japt-h, 4 bytes

ãx ñ

Try it

ãx ñ     :Implicit input of array
ã        :Sub-arrays
ñ     :Sort
:Implicit output of last element

# Python 2, 52 51 bytes

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

Try it online!

• This seems to conflict (the otherwise unnecessary) requirement Don't read anything except stdin, and don't write to anywhere except stdout. Commented Aug 12, 2017 at 13:29

# 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!

# APL, 3129 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

# 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

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

# 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

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

# 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