DIY: Maximum Subarray

Solve the interview question "Maximum Subarray" in this lesson.

Problem statement

Given an integer list, return the sum of the maximum contiguous subarray. The list may contain both positive and negative integers and is unsorted.

Input

The input will be a list of integers. The following is an example input:

[-4, 2, -5, 1, 2, 3, 6, -5, 1]

Output

The output will be the sum of the largest contiguous subarray. For the above input, the output will be:

12

The subarray 1, 2, 3, 6 gives the largest sum 12.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.