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.

Coding exercise

You are required to implement the function maxSubArray(arr) where arr is the provided array for which the subarray needs to be found. The function returns an integer value representing the sum of the largest contiguous subarray present in arr.