Python Forum
In linear time, find the maximum sum of all possible contiguous subarrays
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
In linear time, find the maximum sum of all possible contiguous subarrays
#1
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
Reply
#2
False idea removed.
Reply
#3
(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
Reply
#4
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.
Craig "Ichabod" O'Brien - xenomind.com
I wish you happiness.
Recommended Tutorials: BBCode, functions, classes, text adventures
Reply
#5
(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)
Reply
#6
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.
Reply
#7
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
Reply
#8
(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!
Reply
#9
Hey, this resource I found on Google might be helpful - https://www.interviewbit.com/blog/maximum-subarray-sum/
Reply
#10
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.
Gribouillis likes this post
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 2,188 Mar-05-2021, 04:08 PM
Last Post: SANJIB
  Find frequencies of an audio file at a specific time via librosa jberesford123__ 0 2,280 Oct-21-2020, 01:18 PM
Last Post: jberesford123__
  Find data using a period of time in SQLITE3 SmukasPlays 2 2,144 Jul-30-2020, 02:02 PM
Last Post: SmukasPlays
  Find if time is between start and end time mikke3141 3 2,226 Jan-03-2020, 08:48 PM
Last Post: mikke3141
  Find Maximum Flow for graph with infinite capacities Dav 6 4,197 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