DIY: Maximum Subarray

Problem statement

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

Input

The input will be an array 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.