Note, the required algorithm is known as the Kadane's algorithm and runs in O(n).

Thanks