Maximum subarray problem

Given an array of integers, find the contiguous subarray within it which has the largest sum. Return the sum.

Example Solution

Let array arr equal to [ -2, 1, -3, 4, -1, 2, 1, -5, 4 ]. Subarray with the largest sum is [ 4, -1, 2, 1 ] with sum 6, therefore the solution should return 6.