DIY: Maximum Subarray

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.