Maximum subarray problem: Difference between revisions

Revision as of 19:51, 30 June 2023

Revision as of 23:25, 13 July 2023

Line 62:

Thus, the problem can be solved with the following code,{{sfn|Bentley|1989|p=74}}{{sfn|Gries|1982|p=211}} expressed below in [[Python (programming language)|Python]]. This version of the algorithm will return 0 if the input contains no positive elements (including when the input is empty).

<syntaxhighlight lang="python" line="">

def max_subarray(numbers):

"""#Find the largest sum of any contiguous subarray."""

best_sum = 0

current_sum = 0

for x in numbers:

current_sum = max(0current_sum, current_sum + x)

best_sum = max(best_sum, current_sum)

return best_sum