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 as possible.

Each number in the input array A could be positive, negative, or zero.

For example, for the array of values [−2, 1, −3, 4, −1, 2, 1, −5, 4], the contiguous subarray with the largest sum is [4, −1, 2, 1] with sum 6.

Some properties of this problem are:

1. If the array contains all non-negative numbers, maximum subarray is the entire array.
2. If the array contains all non-positive numbers, then a solution is any subarray of size 1 containing the maximal value of the array (or the empty subarray, if it is permitted).
3. Several different sub-arrays may have the same maximum sum.

This problem can be solved using several different algorithmic techniques, including brute force, divide and conquer, dynamic programming, and reduction to shortest paths.

Algorithm

Kadane's original algorithm solves the problem version when empty subarrays are admitted. It scans the given array A[1...n] from left to right. In the jth step, it computes the subarray with the largest sum ending at j; this sum is maintained in variable current_sum. Moreover, it computes the subarray with the largest sum anywhere in A[1...j], maintained in variable best_sum, and easily obtained as the maximum of all values of current_sum seen so far, line 7 of the algorithm. If empty subarrays are admitted, return max(0, best_sum), otherwise, return best_sum

def max_subarray(numbers, admit_empty):
    """Find the largest sum of any contiguous subarray."""
    best_sum = 0
    current_sum = 0
    for x in numbers:
        current_sum = max(x, current_sum + x)
        best_sum = max(best_sum, current_sum)

    if(admit_empty): return max(0, best_sum)

    return best_sum

As a loop invariant, in the jth step, the old value of current_sum holds the maximum over all of the sum A[i]+...+A[j-1]. Therefore, current_sum + A[j] is the maximum over all of the sum A[i]+ ... +A[j]. To extend the latter maximum to cover also the case i=j+1, it is sufficient to consider also the empty subarray A[j+1 ... j]. This is done in line 6 by assigning max(0, current_sum+A[j]) as the new value of current_sum, which after that holds the maximum over all of the sum A[i]+ ... +A[j].

Computing the best subarray's position

The algorithm can be modified to keep track of the starting and ending indices of the maximum subarray as well:

def max_subarray(numbers):
    """Find a contiguous subarray with the largest sum."""
    best_sum = 0  # or: float('-inf')
    best_start = best_end = 0  # or: None
    current_sum = 0
    for current_end, x in enumerate(numbers):
        if current_sum <= 0:
            # Start a new sequence at the current element
            current_start = current_end
            current_sum = x
        else:
            # Extend the existing sequence with the current element
            current_sum += x

        if current_sum > best_sum:
            best_sum = current_sum
            best_start = current_start
            best_end = current_end + 1  # the +1 is to make 'best_end' match Python's slice convention (endpoint excluded)

    return best_sum, best_start, best_end

Complexity

Because of the way this algorithm uses optimal substructures (the maximum subarray ending at each position is calculated in a simple way from a related but smaller and overlapping subproblem: the maximum subarray ending at the previous position) this algorithm can be viewed as a simple/trivial example of dynamic programming.

The runtime complexity of Kadane's algorithm is O(n).

Thankyou.