Skip to content

Instantly share code, notes, and snippets.

@renzon

renzon/max_subarray_sum.py

Created November 5, 2016 16:36
Show Gist options
  • Save renzon/8c068c68ebb3e93528f2fe6fa313c4ac to your computer and use it in GitHub Desktop.
Save renzon/8c068c68ebb3e93528f2fe6fa313c4ac to your computer and use it in GitHub Desktop.
Download ZIP
Raw
max_subarray_sum.py
def max_subarray_sum(iterator):
iterable = iter(iterator)
try:
next_element = next(iterable)
except StopIteration:
return Exception('Impossible get max sum of empty sequence')
def max_iter(current_sum, max_sum):
try:
next_element = next(iterable)
except StopIteration:
return max_sum
current_sum += next_element
current_sum = max(current_sum, next_element)
return max_iter(current_sum, max(current_sum, max_sum))
return max_iter(next_element, next_element)
print(max_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
print(max_subarray_sum([-2, -1, -3, -4, -1, -2, -1, -5, -4]))
print(max_subarray_sum([-2, -1, -3, -4, -1, -2, 1, -5, -4]))
print(max_subarray_sum([-2, -1, -3, -4, -1, 1, 1, -5, -4]))
@renzon
Copy link
Author

renzon commented Nov 5, 2016 

def max_subarray_sum(iterator):
    iterable = iter(iterator)

    def max_iter(current_sum, max_sum):
        try:
            next_element = next(iterable)
        except StopIteration:
            return max_sum
        current_sum += next_element
        current_sum = max(current_sum, next_element)
        return max_iter(current_sum, max(current_sum, max_sum))

    neg_inf = float('-inf')
    return max_iter(neg_inf, neg_inf)


print(max_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
print(max_subarray_sum([-2, -1, -3, -4, -1, -2, -1, -5, -4]))
print(max_subarray_sum([-2, -1, -3, -4, -1, -2, 1, -5, -4]))
print(max_subarray_sum([-2, -1, -3, -4, -1, 1, 1, -5, -4]))
print(max_subarray_sum([]))

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment