Maximum Subarray

Difficulty: Medium · Topic: Arrays & strings

Given an integer array nums, find the contiguous subarray (containing at least one number) with the largest sum and return that sum.

Examples

max_subarray([-2,1,-3,4,-1,2,1,-5,4])
→ 6

[4, -1, 2, 1] sums to 6.

max_subarray([1])
→ 1

max_subarray([5,4,-1,7,8])
→ 23

Target complexity: time O(n), space O(1)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.