Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.
More practice:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
@tag-array

Algorithm

The O(n) solution is to define two variables res and curSum, where res holds the final result to be returned, that is, the sum of the largest sub-array.

The initial value of curSum is 0, and each traversal of a number num, compare curSum + num and num. Store the larger value in curSum, and then store the larger value in res and curSum in res, and so on until the entire array is traversed, and the value of the largest sub-array can be obtained in res.