7
\$\begingroup\$

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!

Leaderboard

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>

\$\endgroup\$
11
  • 1
    \$\begingroup\$ ight! Thanks so much! \$\endgroup\$
    – user116868
    Feb 14 at 11:34
  • 1
    \$\begingroup\$ Is this restricted-complexity or can we brute force it? Brute force will be much shorter than the efficient algorithm in most languages \$\endgroup\$
    – mousetail
    Feb 14 at 11:35
  • 1
    \$\begingroup\$ @mousetail you are given the option to use brute force, I just recommended the algorithm to be used. You can use brute forcing. \$\endgroup\$
    – user116868
    Feb 14 at 11:38
  • 3
    \$\begingroup\$ 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. \$\endgroup\$
    – chunes
    Feb 14 at 11:55
  • 4
    \$\begingroup\$ Is empty array an subarray? \$\endgroup\$
    – tsh
    Feb 14 at 12:54

18 Answers 18

5
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ slay! The shortest answer possible \$\endgroup\$
    – user116868
    Feb 14 at 18:02
  • \$\begingroup\$ Nice! I didn't check for that command! \$\endgroup\$
    – The Thonnu
    Feb 14 at 18:08
4
\$\begingroup\$

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!

\$\endgroup\$
1
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – Adám
    Feb 14 at 11:55
3
\$\begingroup\$

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 ⌈/.

\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$
    – user116868
    Feb 14 at 11:52
  • \$\begingroup\$ @AitzazImtiaz I've added Kadane's algorithm for reference. \$\endgroup\$
    – Adám
    Feb 14 at 12:00
3
\$\begingroup\$

Husk, 3 bytes

►ΣQ

Try it online!

►       # maximum by
 Σ      # sum
        # of 
  Q     # all contiguous subarrays
\$\endgroup\$
2
\$\begingroup\$

Vyxal G, 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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Adám
    Feb 14 at 11:55
  • \$\begingroup\$ @Adám fixed and saved 4 bytes \$\endgroup\$
    – The Thonnu
    Feb 14 at 12:11
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ Actually the question states to find the sum, not the subarray. So this would be ãx ñ \$\endgroup\$
    – noodle man
    Feb 14 at 15:58
2
\$\begingroup\$

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.

\$\endgroup\$
11
  • \$\begingroup\$ 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# \$\endgroup\$ Feb 24 at 0:08
  • \$\begingroup\$ @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. \$\endgroup\$ Feb 24 at 5:26
  • \$\begingroup\$ 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) \$\endgroup\$ Feb 25 at 3:54
  • \$\begingroup\$ 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) \$\endgroup\$ Feb 25 at 3:54
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ Mar 18 at 18:47
1
\$\begingroup\$

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!

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

Wolfram Language (Mathematica), 24 bytes

Max[Tr/@Subsequences@#]&

Try it online!

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

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!

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

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!

\$\endgroup\$
5
  • \$\begingroup\$ Gives 0 if all numbers are negative integers but must give the biggest negative integer \$\endgroup\$
    – EzioMercer
    Feb 14 at 20:43
  • \$\begingroup\$ @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. \$\endgroup\$
    – Arnauld
    Feb 14 at 20:51
  • \$\begingroup\$ 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 \$\endgroup\$
    – EzioMercer
    Feb 14 at 21:01
  • 1
    \$\begingroup\$ @EzioMercer What I mean is that a subarray of length 0 can be extracted from any input array, leading to a sum of 0. \$\endgroup\$
    – Arnauld
    Feb 14 at 21:03
  • \$\begingroup\$ I got your point :) \$\endgroup\$
    – EzioMercer
    Feb 14 at 21:05
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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

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

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

\$\endgroup\$
2
  • \$\begingroup\$ Removing one lost pair of parens in the first one results in -1. \$\endgroup\$
    – pajonk
    Feb 16 at 18:22
  • \$\begingroup\$ @pajonk - how did I miss that? Thanks! \$\endgroup\$ Feb 16 at 21:34
0
\$\begingroup\$

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)
\$\endgroup\$
0
\$\begingroup\$

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

enter image description here

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

Charcoal, 14 bytes

I⌈Eθ⌈Eθ↨¹✂θκ⊕μ

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

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

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

\$\endgroup\$