Kadane's Algorithm

This algorithm solves the Maximum Subarray problem. It is a Dynamic programming solution.

maxSum[i] = max(maxSum[i-1] + input[i], input[i])

Leetcode