1. Start with curSum = 0 and maxSum = 0.
2. Traverse the array elements, from i = 0 to n-1, where n is the length of the array.
a. Keep adding array elements to curSum till curSum >= 0 and update maxSum to curSum if maxSum < curSum.
b. As soon as curSum becomes < 0, reset curSum = 0.
3. Finally return maxSum.
This is known as Kadane's algorithm.
The above method does not take care of the case when all the elements in the array are negative.
In this case, we can modify the algorithm, to keep a flag hasAllNegativeNumbers initialized to true.
If a positive or 0 element is seen in the array, then set hasAllNegativeNumbers = false.
Also, while traversing the array, keep track of maximum negative element.
Finally, if hasAllNegativeNumbers is true, then return maxNegativeSum, else return maxSum.