Kadane's Algorithm

Maximum sum subarray problem is the task of finding a contiguous subarray with the largest sum, within a given one-dimensional array A[1...n] of numbers. Formally, the task is to find indices i and j with 1 <= i <= j <= n such that the sum is large ...