Given an array of integers, find the contiguous subarray within it which has the largest sum. Return the sum.
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
.