Challenge: Finding the Largest Sum Subarray

Problem

Given an array of positive and negative integers, find a contiguous subarray whose sum (sum of its elements) is the maximum.

Input

An integer array.

Output

Maximum subarray sum.

Sample input

array = { 1, -2, 3, 4, -4, 6, -14, 6, 2 }

Sample output

sum = 9

Let’s look at the illustration to better understand how it works.