Find the largest sum of any contiguous subarray of the array [duplicate]

Let's say you are given an integer array. Create a function to determine the largest sum of any array's adjacent subarrays. For instance, the contiguous subarray with the largest sum is [4, -1, 2, 1] in the array [-2, 1, -3, 4, -1, 2, 1, -5, 4].

You can employ a variant of Kadane's algorithm to resolve this issue. The steps are as follows:

1. Set max_so_far and max_ending_here, two variables, to the first array element.
2. From the second element all the way to the end, traverse the array.
3. Update the max_ending_here variable for each element by either adding the current element to it or setting it to the current element if it is larger than the sum of the previous elements.
4. If the max_ending_here variable is larger than the max_so_far variable, update it.
5. The max_so_far variable holds the largest sum of any contiguous subarray after traversing the entire array.

The steps are optional to perform if you may like. The best one which wins is the shortest in length!

var QUESTION_ID=257808,OVERRIDE_USER=116868;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px} /* font fix */ body {font-family: Arial,"Helvetica Neue",Helvetica,sans-serif;} /* #language-list x-pos fix */ #answer-list {margin-right: 200px;}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

• ight! Thanks so much!
– user116868
Feb 14, 2023 at 11:34
• Is this restricted-complexity or can we brute force it? Brute force will be much shorter than the efficient algorithm in most languages Feb 14, 2023 at 11:35
• @mousetail you are given the option to use brute force, I just recommended the algorithm to be used. You can use brute forcing.
– user116868
Feb 14, 2023 at 11:38
• This question has already been asked many times. Here are two of them. codegolf.stackexchange.com/questions/3059/… codegolf.stackexchange.com/questions/138697/maximum-sub-array I am confident there are many more. Feb 14, 2023 at 11:55
• Is empty array an subarray?
– tsh
Feb 14, 2023 at 12:54

Vyxal G, 3 bytes

ÞSṠ


This is my first Vyxal answer but I'm already outgolfing TheThonnu lol

Try it Online!

ÞSṠ
ÞS  : Sublists
Ṡ : Vectorized sum (sum each)
: -G: Max

• slay! The shortest answer possible
– user116868
Feb 14, 2023 at 18:02
• Nice! I didn't check for that command! Feb 14, 2023 at 18:08

Python, 69 bytes

lambda x:max(sum(x[a:b])for a in range(len(x))for b in range(len(x)))


Attempt This Online!

Python, 74 bytes

Outputs the list

lambda x:max((x[a:b]for a in range(len(x))for b in range(len(x))),key=sum)


Attempt This Online!

• As per OP's "Create a function to determine the largest sum of any array's adjacent subarrays.", you should return the largest sum, not the subarray.
Feb 14, 2023 at 11:55

APL (Dyalog Unicode), 9 bytes

Anonymous tacit prefix function.

⌈/∘∊⍋+/¨⊂


Try it online!

⊂ on the entire input:

+/¨ sum sub-sequences of each of the following lengths:

⍋ the grade (permutation that would sort, but the order doesn't matter; we just need all the indices as lengths)

∘∊enlist (flatten), and then:

⌈/ find the maximum (lit. maximum reduction)

For reference, Kadane's algorithm can be found on APLcart, but is much longer:

{s←0 ⋄ ⌈/{s⊢←0⌈s+⍵}¨⍵}


This sets the maximum sum with s←0 then, for each element {}¨⍵ we update the sum s⊢← with the maximum of zero and 0⌈ the sum plus that element s+⍵. Finally, we find the maximum ⌈/.

• This is what I exactly wanted, splendid job! I definitely wanted to return an integer in output, and checked back that the output must be 6.
– user116868
Feb 14, 2023 at 11:52
Feb 14, 2023 at 12:00

Husk, 3 bytes

►ΣQ


Try it online!

►       # maximum by
Σ      # sum
# of
Q     # all contiguous subarrays


VyxalG, 9 bytes

Lʀ:Ẋƛ?$i∑  Try it Online! Explanation Lʀ:Ẋƛ?$i∑  # Implicit input
Lʀ         # Length range
:Ẋ       # Cartesian product with itself
ƛ      # Map:
?$i # Slice input ∑ # Sum # G flag gets maximum  • As per OP's "Create a function to determine the largest sum of any array's adjacent subarrays.", you should return the largest sum, not the subarray. – Adám Feb 14, 2023 at 11:55 • @Adám fixed and saved 4 bytes Feb 14, 2023 at 12:11 Brachylog, 5 bytes sᶠ+ᵐ⌉  Try it online! Please note that the negative symbol for negative numbers is the underscore _ in Brachylog, not the standard dash -. Explanation sᶠ Find all sublists of consecutive elements +ᵐ Map sum ⌉ Get the max  Japt-h, 4 bytes Because the required ouput is not clear from the spec, the first solution below outputs the sub-array, while the second outputs its sum. ã ñx  Try it ãx Í  Try it ã ñx :Implicit input of array ã :Sub-arrays ñ :Sort by x : Sum :Implicit output of last element  ãx Í :Implicit input of array ã :Sub-arrays x :Reduced by addition Í :Sort :Implicit output of last element  • Actually the question states to find the sum, not the subarray. So this would be ãx ñ Feb 14, 2023 at 15:58 Excel, 70 74 bytes =LET(b,SEQUENCE(ROWS(A1#)),MAX(SUBTOTAL(9,OFFSET(A1#,b-1,,TRANSPOSE(b)))))  where A1# is a vertical spill range comprising the values from the array. • Unfortunately, you cannot assume a named range for input in worksheet based languages (meta link). The best way to take array inputs is to use the Spilled Range Operator (#) and assume that the array begins at cell A1, ie take input from A1# Feb 24, 2023 at 0:08 • @TaylorAlexRaine Thanks, will amend. Before I do so, however, could you just clarify why referencing a spilled range is permissible? Based on the criteria you give in a comment in the linked post - "1 - it requires user action that is neither self explanatory to someone who does not know these languages nor standardized, which leads to confusion in implementation and 2 - It corresponds to a distinct programmable action that you are bypassing without contributing anything to the bytecount", I would've thought that the use of a spilled range would fail at least point 1, if not also point 2. Feb 24, 2023 at 5:26 • Jos, this just comes down to what the community considers standard I/O for each language, both at the program and function level. For more traditional languages this is pretty cut and dry - STDIN/STDOUT, files for programs, and passed variables for functions. But Excel, well is odd. When we decided the standards, lambda functions and dynamic arrays did not exist - there was no concept of a passed variable, only referenced ranges (1/5) Feb 25, 2023 at 3:54 • Named ranges were initially used by some users to reduce their bytecounts, but this soon led to issues. One that was common was using ranges to refer to multiple areas (ie named range a referring to A1:C3,D4:F6). This negated the challenge of several otherwise fun problems and was eventually deemed to be against the spirit of codegolf. There were two key arguements for banning this - 1. assuming that input was taken by a predefined variable was already disallowed in almost all other languages; and - 2. it corresponded programmable actions being manually bypassed by the user. (2/5) Feb 25, 2023 at 3:54 • @TaylorAlexRaine So they see this comment. I'm not familiar with excel, but see no reason that wouldn't be allowed. Regardless, you still need to edit your answer to not use a named range. Mar 18, 2023 at 18:47 Python 3.8 (pre-release), 65 bytes f=lambda a,x=0,y=0:max(x-y,len(a)and f(a[1:],x:=x+a[0],min(x,y)))  Try it online! Wolfram Language (Mathematica), 24 bytes Max[Tr/@Subsequences@#]&  Try it online! Python, 41 bytes lambda a,x=0:max(x:=max(c+x,0)for c in a)  Attempt This Online! Version that can handle empty input: Python, 43 bytes lambda a,x=0:max(x:=c+x*(x>0)for c in[0]+a)  Attempt This Online! JavaScript (ES6), 41 bytes Like several other answers, this assumes that the empty array is a valid subarray. a=>Math.max(...a.map(v=>s=v>-s&&s+v,s=0))  Try it online! • Gives 0 if all numbers are negative integers but must give the biggest negative integer Feb 14, 2023 at 20:43 • @EzioMercer Why should it? Considering that we can select an empty subarray with sum 0 is just as sensible. The OP must clarify that point but has not yet answered tsh's question in the comments. Feb 14, 2023 at 20:51 • Why this depend on empty array? [-1, -2, -3] - in this example the biggest sum is -1 how it can be a 0? I agree that an empty array is an edge case of the problem, but if we have elements it can't be anything but the largest sum of elements Feb 14, 2023 at 21:01 • @EzioMercer What I mean is that a subarray of length 0 can be extracted from any input array, leading to a sum of 0. Feb 14, 2023 at 21:03 • I got your point :) Feb 14, 2023 at 21:05 05AB1E, 3 bytes ŒOZ  Try it online! TIL that there's a "sublists" command in both 05AB1E and Vyxal! Œ # Sublists O # Sum each Z # Maximum  JavaScript, 42 bytes a=>a.map(s=m=n=>m=m>(s=0<s?n+s:n)?m:s)|m  Try it: f=a=>a.map(s=m=n=>m=m>(s=0<s?n+s:n)?m:s)|m ;[ [-2, 1, -3, 4, -1, 2, 1, -5, 4], // 6 [1], // 1 [1, 2, 3, 4, 5, 6, 7], // 28 [-1, -2, -3, -4, -5, -6, -7], // -1 [-3, -2, -1, 0, 1, 2, 3], // 6 ].map(a=>console.log(f(a))) UPD 45 -> 42 Thanks to Arnauld for the tip to reduce bytes count R, 46 45 bytes Edit: -1 byte thanks to pajonk \(s){b=0;for(x in s)b=max(F<-max(x,F+x),b);b}  Attempt This Online! Outputs the sum of the subarray with the largest sum (as requested in the second sentence of the question) R, 59 bytes \(s,+=sum,b={}){for(x in s)if(+(F=c(F[+F>0],x))>+b)b=F;b}  Attempt This Online! Outputs the subarray with the largest sum (as in the example in the third sentence of the question). • Removing one lost pair of parens in the first one results in -1. Feb 16, 2023 at 18:22 • @pajonk - how did I miss that? Thanks! Feb 16, 2023 at 21:34 Pyth, 6 bytes eSsM.:  Try it online! Explanation eSsM.:Q # implicitly add Q # implicitly assign Q = eval(input()) .:Q # list all subarrays of Q sM # map to their sums eS # sort and take the last value (the largest sum)  ><> (Fish), 48 bytes 00i:?v/::0$0)?$~-{20. +i}-1/\&~$?(@:\$@:&:
;n~~/


Try it

I thought Kadane's algorithm would always be longer but for ><>, which lacks normal array manipulation, it's actually shorter.

Takes input as a length-prefixed array.

Charcoal, 14 bytes

Ｉ⌈Ｅθ⌈Ｅθ↨¹✂θκ⊕μ


Try it online! Link is to verbose version of code. Explanation:

   θ            Input array
Ｅ             Map over elements
θ         Input array
Ｅ          Map over elements
✂θκ⊕μ  Inclusive slice of elements
↨¹       Take the sum
⌈           Take the maximum
⌈              Take the maximum
Ｉ               Cast to string
Implicitly print


(Using "base 1" to take the sum as that returns 0 for empty lists.)