Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. A subarray is a contiguous part of an array.
Sample Input:
[-2, 1, -3, 4, -1, 2, 1, -5, 4]
Sample Output:
6
Hints
Hint 1
Use Kadane's algorithm
Hint 2
Keep track of the maximum sum ending at current position
