Per an interview question offered as a "question of the day," how would you find, given an array of integers, the maximum sum of all possible contiguous subarrays
in linear time. I'm pretty sure my solution is not in
linear time, since I have a for-loop inside another for-loop:
def max_subarray_sum(arr):
"""Given an array of integers, find the maximum sum
of all possible contiguous subarrays of the array"""
# A variable to store the largest sum
max_sum = 0
# Loop through every possible contiguous subarray
for mindex in range(0, len(arr)):
for maxdex in range(mindex + 1, len(arr) + 1):
# A variable to store the sum of the
# integers in each subarray
subarray_sum = 0
# Add all the integers in the subarray together
# and store the result in subarray_sum
for each_int in arr[mindex:maxdex]:
subarray_sum += each_int
# If a subarray's sum is larger than the number
# stored in the max_sum variable, update max_sum
# with the new value
if subarray_sum > max_sum:
max_sum = subarray_sum
# Return the largest sum found among all contiguous subarrays
return max_sum
print(max_subarray_sum([34, -50, 42, 14, -5, 86]))
# Result: 137
# Correct Result: 137
(Oct-01-2019, 11:37 PM)Gribouillis Wrote: [ -> ]False idea removed.
I don't understand your answer. Can you elaborate?
Update: Oh, wait. You gave an answer and then deleted it. Sorry, I'm dense sometimes. XD
I'm confused. The array as a whole is a subarray of the array, right? So the sum of all the positive numbers in the array is the maximum possible sum of all the possible subarrays, isn't it? Any other subarray made from removing a positive number or adding a negative number would have a smaller sum.
(Oct-02-2019, 01:05 AM)ichabod801 Wrote: [ -> ]I'm confused. The array as a whole is a subarray of the array, right? So the sum of all the positive numbers in the array is the maximum possible sum of all the possible subarrays, isn't it? Any other subarray made from removing a positive number or adding a negative number would have a smaller sum.
The keyword is "contiguous." The integers have to be next to each other in the array. You can't pick out only the positive integers.
Thus, the largest sum in the above example is the subarray [42, 14, -5, 86], which is 137. The sum of the entire array is smaller: 121.
Someone offered this, but I haven't been able to test or think through it yet:
def max_sum_contiguous(arr):
running_totals = []
running_total = 0
for i, value in enumerate(arr):
if value > -running_total:
running_total += value
else:
running_total = 0
running_totals.append(running_total)
return max(running_totals)
It works. I tested the function that runs in linear time against my quadratic-time solution 10,000 times, and both give the same result, no matter what integers are in the array:
import random
# Given an array of integers, find the maximum sum
# of all possible contiguous subarrays of the array
def max_subarray_sum_quadratic(arr):
max_sum = 0
for mindex in range(0, len(arr)):
for maxdex in range(mindex + 1, len(arr) + 1):
subarray_sum = 0
for each_int in arr[mindex:maxdex]:
subarray_sum += each_int
if subarray_sum > max_sum:
max_sum = subarray_sum
return max_sum
def max_subarray_sum_linear(arr):
running_totals = []
running_total = 0
for value in arr:
if value > -running_total:
running_total += value
else:
running_total = 0
running_totals.append(running_total)
return max(running_totals)
for r in range(10000):
whole_array = []
for r2 in range(6):
whole_array.append(random.randint(-100, 100))
if max_subarray_sum_quadratic(whole_array) != max_subarray_sum_linear(whole_array):
print("\nArray:", whole_array)
print(max_subarray_sum_quadratic(whole_array), "quadratic")
print(max_subarray_sum_linear(whole_array), "linear")Now I just have to figure out how the linear-time function is working exactly. I'm slow at math.
It seems easy if you define
s[j] = sum(arr[i] for i in range(j)) because if the maximum sum of contiguous subarrays is reached for a the range(a, b) of indices, with a <= b, then this sum is
s[b] - s[a] and for all c <= b one has
s[b] - s[c] <= s[b] - s[a] which means that
s[a] <= s[c], hence s[a] is the minimum value of
s for all indices smaller than b. Hence the algorithm
start with mv = 0 and sv = 0 and best = 0
for b in range(n):
sv += arr[b]
mv = min(mv, sv)
best = max(best, sv - mv)
return best
(Oct-02-2019, 09:04 PM)Gribouillis Wrote: [ -> ]It seems easy if you define s[j] = sum(arr[i] for i in range(j)) because if the maximum sum of contiguous subarrays is reached for a the range(a, b) of indices, with a <= b, then this sum is s[b] - s[a] and for all c <= b one has s[b] - s[c] <= s[b] - s[a] which means that s[a] <= s[c], hence s[a] is the minimum value of s for all indices smaller than b. Hence the algorithm
start with mv = 0 and sv = 0 and best = 0
for b in range(n):
sv += arr[b]
mv = min(mv, sv)
best = max(best, sv - mv)
return best
I didn't understand most of the that, but I'm going to work on it till I do!
import random
def mymax(array):
'''Find sub-array of array with the largest sum.
Return (sum, start_index, end_index)
'''
subsum = start = 0
maxsum = [subsum, start, start]
for index, value in enumerate(array):
subsum += value
if subsum > maxsum[0]:
# Found a new maximum
maxsum = [subsum, start, index]
elif subsum <= 0:
# No future maxsums will contain anything from array[:index]. Look for max sub_array sum for array[i+1:]
subsum = 0
start = index + 1
return maxsum
def gribmax(array):
'''Solution from Griboullis for finding greatest sum of consecutive array values'''
mv = sv = best = 0
for value in array:
sv += value
mv = min(mv, sv)
best = max(best, sv-mv)
return best
x = random.choices(range(-100, 100), k=30)
print(x)
print(mymax(x))
print(gribmax(x))My solution and Griboullis' solution agree when run on 100,000 different random arrays of length 100.