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

Question

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>

Answer 1

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

Answer 2

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!

Answer 3

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

Answer 4

Husk, 3 bytes

►ΣQ

Try it online!

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

Answer 5

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

Answer 6

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

Answer 7

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

Answer 8

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.

Answer 9

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!

Answer 10

Wolfram Language (Mathematica), 24 bytes

Max[Tr/@Subsequences@#]&

Try it online!

Answer 11

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!

Answer 12

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!

Answer 13

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

Answer 14

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

Answer 15

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

Answer 16

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)

Answer 17

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

Answer 18

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