##### In linear time, find the maximum sum of all possible contiguous subarrays
 In linear time, find the maximum sum of all possible contiguous subarrays deanhystad So-and-so of the Yard Posts: 2,695 Threads: 12 Joined: Feb 2020 Reputation: Oct-28-2021, 09:02 PM If you have two contiguous slices, a and b, the sum of a + b is only greater than the sum of slice b if the sum of slice a is positive. In other words, the slice with the maximum sum will only start with slice a if the sum of slice a is positive. In my program subsum is the sum of slice a, and value is the sum of slice b (a slice containing just the next value). The program adds values to slice a, checking if the new sum is the highest sum seen so far. If the sum of slice a is less than zero it is discarded because including a will only decrease the sum of future slices. I also discard a when the sum of a is zero, choosing shorter slices over longer slices of the same value. This is a good interview question. Reply Posts: 3,294 Threads: 45 Joined: Jan 2018 Reputation: Oct-29-2021, 06:54 AM (This post was last modified: Oct-29-2021, 07:43 AM by Gribouillis.) A new version for python >= 3.8 ```from operator import add, sub from itertools import accumulate, tee def gribmax2(iterable): s, t = tee(accumulate(iterable, add, initial=0)) return max(map(sub, s, accumulate(t, min)))```It seems to agree with Deanhystad's version on 100000 arrays of length 100 with values in the range(-1000, 1000). It took me a while to reach this quintessence of a function. I hope it will become a must in interviews from now on! Reply DPaul Minister of Silly Walks Posts: 411 Threads: 47 Joined: Dec 2017 Reputation: Oct-29-2021, 03:48 PM (This post was last modified: Oct-29-2021, 03:50 PM by DPaul.) @ Griboullis, @ deanhystad From time to time, an interesting challenge pops up :-) For the aged students amongst us, could you provide one or two solutions, from arrays len(100), that you know are correct. That way we can test our home-grown algorithms. As always, I get the feeling that this is not so complicated, but I am often wrong. Thanks 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 deanhystad So-and-so of the Yard Posts: 2,695 Threads: 12 Joined: Feb 2020 Reputation: Oct-29-2021, 04:12 PM (This post was last modified: Oct-29-2021, 04:12 PM by deanhystad.) Generate random lists of numbers and use the posted code(s) to compute the answer. You don't need an answer sheet when you have code that generates the correct answer. Personally I think a lot of insight is gained by solving this problem by hand. I blanked on this problem until I wrote a list of numbers and a list of sums. I looked at that for about 10 seconds and the solution was immediately obvious. Reply DPaul Minister of Silly Walks Posts: 411 Threads: 47 Joined: Dec 2017 Reputation: Oct-29-2021, 05:19 PM (Oct-29-2021, 04:12 PM)deanhystad Wrote: Generate random lists of numbers and use the posted code(s) to compute the answer. You don't need an answer sheet when you have code that generates the correct answer. Personally I think a lot of insight is gained by solving this problem by hand. I blanked on this problem until I wrote a list of numbers and a list of sums. I looked at that for about 10 seconds and the solution was immediately obvious. Well , I did that of course, but maybe I'm missing something. What should x = [-1,-2,-3,-4] yield ? As I understand it : -1 Or are single values not allowed , although it is a "subarray". 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 deanhystad So-and-so of the Yard Posts: 2,695 Threads: 12 Joined: Feb 2020 Reputation: Oct-29-2021, 05:59 PM There is an error in my code in that it starts with the assumption that the max sum will be greater than 0. It would be better if it initialized maxsum to [array[0], start, start]. That allows it to work for the case were all numbers in the list are negative. The correct answer for [-1, -2, -3, -4] is [-1, -0, 0] for my code. I'm not sure how to go about fixing Griboullis' code. The problem is that with all negative numbers, sv and min(mv, sv) are always the same, so best = max(best, 0). Starting with max = array[0] does not fix the problem. Reply DPaul Minister of Silly Walks Posts: 411 Threads: 47 Joined: Dec 2017 Reputation: Oct-29-2021, 06:25 PM (Oct-29-2021, 05:59 PM)deanhystad Wrote: There is an error in my code in that it starts with the assumption that the max sum will be greater than 0. It would be better if it initialized maxsum to [array[0], start, start]. That allows it to work for the case were all numbers in the list are negative. The correct answer for [-1, -2, -3, -4] is [-1, -0, 0] for my code. I'm not sure how to go about fixing Griboullis' code. The problem is that with all negative numbers, sv and min(mv, sv) are always the same, so best = max(best, 0). Starting with max = array[0] does not fix the problem. That's why I asked the question. Still, I'm checking my solution for larger arrays, will publish it when i'm sure. 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 Posts: 3,294 Threads: 45 Joined: Jan 2018 Reputation: Oct-29-2021, 07:08 PM For me the correct answer for `[-1, -2, -3, -4]` is 0, the sum of the empty list. Reply DPaul Minister of Silly Walks Posts: 411 Threads: 47 Joined: Dec 2017 Reputation: Oct-30-2021, 05:38 AM (This post was last modified: Oct-30-2021, 05:39 AM by DPaul.) (Oct-29-2021, 07:08 PM)Gribouillis Wrote: For me the correct answer for `[-1, -2, -3, -4]` is 0, the sum of the empty list. Could you elaborate please? Do you see this as a mathematical concept or a practical consideration ? Because the random generator (-100,100) could very well produce an all negative array. thx, 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 DPaul Minister of Silly Walks Posts: 411 Threads: 47 Joined: Dec 2017 Reputation: Oct-30-2021, 06:43 AM I ran several tests with both proposed codes, up to len(arr) = 100, and I get the same results. So for what it's worth: ```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)])) print(max(maxArr)) ```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

 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,241 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