##### In linear time, find the maximum sum of all possible contiguous subarrays
 In linear time, find the maximum sum of all possible contiguous subarrays Posts: 3,294 Threads: 45 Joined: Jan 2018 Reputation: Oct-30-2021, 08:42 AM @DPaul, your implementation is 0(n^2), try to print the length of maxArr to see it. I think my function can be modified like so to allow only non empty sublists: ```def gribmax3(array): s, t = tee(accumulate(array, add, initial=0)) next(s) return max(map(sub, s, accumulate(t, min)))```For your question regarding gribmax2() yes, mathematically one usually defines an empty sum of numbers to be equal to 0. However this is purely conventional. Python does the same sometimes ```>>> sum([]) 0``` Reply deanhystad So-and-so of the Yard Posts: 2,695 Threads: 12 Joined: Feb 2020 Reputation: Oct-30-2021, 02:41 PM (This post was last modified: Oct-30-2021, 02:41 PM by deanhystad.) (Oct-30-2021, 05:38 AM)DPaul Wrote: Because the random generator (-100,100) could very well produce an all negative array.Possible, sure, but very well? Odds are 1 in 2^100 for a len(100) array. "Very well" sounds like a synonym for "reasonable possibility". Reply Posts: 3,294 Threads: 45 Joined: Jan 2018 Reputation: Oct-30-2021, 05:05 PM (This post was last modified: Oct-30-2021, 05:05 PM by Gribouillis.) deanhystad Wrote:"Very well" sounds like a synonym for "reasonable possibility".By generating a list every NANOsecond, it takes 40 TRILLION years to generate 2**100 lists. ```i>>> nanosec_per_trillion_year = 1e12 * 365.25 * 24 * 3600 * 1e9 >>> 2**100 / nanosec_per_trillion_year 40.16942353753864```That's more than 3000 times the estimated age of the universe, assuming it means something. Reply deanhystad So-and-so of the Yard Posts: 2,695 Threads: 12 Joined: Feb 2020 Reputation: Oct-30-2021, 05:12 PM But it is still possible. Reply DPaul Minister of Silly Walks Posts: 411 Threads: 47 Joined: Dec 2017 Reputation: Oct-30-2021, 05:20 PM Point taken. There is critique on my command of the Queen's English. Therefore, in my post, read "very well" as "occasionally". Paul It is more important to do the right thing, than to do the thing right.(P.Drucker) Better is the enemy of good. (Montesquieu) = French version for 'kiss'. Reply darter Programmer named Tim Posts: 13 Threads: 8 Joined: Nov 2016 Reputation: Oct-31-2021, 03:45 PM I was having a bit of trouble understanding what was meant by this challenge and compared it to maybe the intended(?) idea as posted on google: Question as posted here is: # Given an array of integers, find the maximum sum # of all possible contiguous subarrays of the array Question as posted on google is: Given an array of integers, the task is to find the maximum subarray sum possible of all the non-empty subarrays. As posted here the idea would be simply to sum all of the subtotals from every possible sub-array- but then the use of the word 'maximum' becomes superfluous - hence my confusion. (When I read 'sum of' I would normally expect to just add up whatever comes next ie, ' all possible contiguous subarrays' So I think we are just looking for the subarray of contiguous values that produces the largest value. Reply Posts: 3,294 Threads: 45 Joined: Jan 2018 Reputation: Oct-31-2021, 05:30 PM (Oct-31-2021, 03:45 PM)darter Wrote: So I think we are just looking for the subarray of contiguous values that produces the largest value.There is a tiny difference. We are only looking for the largest value, not the subarray that produces this value. It is the same difference that exists between a max and an argmax. Deanhystad's code above returns both the subarray and its sum. Reply DPaul Minister of Silly Walks Posts: 411 Threads: 47 Joined: Dec 2017 Reputation: Nov-01-2021, 08:39 AM Hi, I made a small tweak, so that the sum array does not get very large. This does not take away that my loop x loop version is obviously slower than the other versions. I did some timing measurements:(100_000 loops of random (-100,100) array length 30.) My version is about 20 times slower than the others (1.4 secs against almost 25 secs) How exponential is it ? Random arrays of 5: 1.12 secs 10 : 3.20 secs 20: 11.0 secs 30: 24.9 secs 50: 76 secs I have some work cut out. Paul ``` arr = random.choices(range(-100, 100), k=50) maxArr = [max(arr)] for number in range(len(arr)): for grouping in range(2,len(arr)-number+1): maxArr.append(sum(arr[number:(number+grouping)])) maxArr = [max(maxArr)]``` It is more important to do the right thing, than to do the thing right.(P.Drucker) Better is the enemy of good. (Montesquieu) = French version for 'kiss'. Reply DPaul Minister of Silly Walks Posts: 411 Threads: 47 Joined: Dec 2017 Reputation: Nov-04-2021, 07:37 AM Hi, The nested loop approach ("brute force") will produce the goods, but for the (-100/+100, array = 30) case it will take 24+ seconds.(100_000 iterations) I set out to see if this approach could be tuned to produce more acceptable results. And yes, if you prepare the initial array in such a way that it will only test "valid" candidate subarrays, the processing time drops to +/- 4.8 secs. (Doubling the arrays : 5-10-20... will roughly double the processing time.) Looking for inspiration to cut the 4.8 secs further... ```maxArr = [max(arr)] idxStarts, idxEnds = [],[] for idx, number in enumerate(arr): if number > 0: if idx == 0 or arr[idx-1] < 0: idxStarts.append(idx) if idx == len(arr)-1 or arr[idx+1] < 0: idxEnds.append(idx) for idxfrom in idxStarts: for idxto in idxEnds: maxArr.append(sum(arr[idxfrom:idxto +1])) maxArr = [max(maxArr)]``` It is more important to do the right thing, than to do the thing right.(P.Drucker) Better is the enemy of good. (Montesquieu) = French version for 'kiss'. Reply DPaul Minister of Silly Walks Posts: 411 Threads: 47 Joined: Dec 2017 Reputation: Nov-07-2021, 08:39 AM (This post was last modified: Nov-07-2021, 08:39 AM by DPaul.) Hi, I gave this "interview question" some considerable thought, because I want to get hired next time. My basic idea was to reduce the size of the original array, effectively reducing the number of possible subarrays. There are about 10 rules you can formulate: e.g. a candidate subarray cannot start with a negative number or zero etc.. (You need to make proviso's for all negative arrays, which happen frequently if you do (-100, 10, k=30) This is a dummy example: ``````Output:arr = [-1,-2, 3, 4, 5,-6, 7, 8, 0,-9,-10, 11,-12] newarr = [ 12,-6, 15,-19, 11]``````Unfortunately, every "if" comes with a penalty of about 0.1 secs in 100_000 runs. It is a trade-off, and I was not able to write a "reducing" algorithm, that was fast enough to my taste. (Another interview question?) So I ended up with a solution along the lines what was proposed above, yielding about 1.5 secs for 100_000 runs. Paul ```maxArr = [max(arr)] subarr = 0 for number in arr: subarr += number if subarr > 0: maxArr.append(subarr) else: subarr = 0 maxarr = max(maxArr)``` Gribouillis likes this post It is more important to do the right thing, than to do the thing right.(P.Drucker) Better is the enemy of good. (Montesquieu) = French version for 'kiss'. Reply

 Possibly Related Threads… Thread Author Replies Views Last Post find the header location in a .bin file without reading the whole file at a time SANJIB 0 881 Mar-05-2021, 04:08 PM Last Post: SANJIB Find frequencies of an audio file at a specific time via librosa jberesford123__ 0 802 Oct-21-2020, 01:18 PM Last Post: jberesford123__ Find data using a period of time in SQLITE3 SmukasPlays 2 1,050 Jul-30-2020, 02:02 PM Last Post: SmukasPlays Find if time is between start and end time mikke3141 3 1,240 Jan-03-2020, 08:48 PM Last Post: mikke3141 Find Maximum Flow for graph with infinite capacities Dav 6 2,306 Apr-16-2019, 02:08 PM Last Post: Dav

Forum Jump:

### User Panel Messages

##### Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020