Given an array of integers, the task is to find the contiguous subarray (containing at least one number) that has the largest sum and return its sum. For example, given the array [-2, 1, -3, 4, -1, 2, 1, -5, 4], the contiguous subarray with the largest sum is [4, -1, 2, 1], and the sum is 6.