Maximum subarray problem

maximum_subarray_problem.md

Maximum subarray problem

Find the contiguous subarray within a one-dimensional array of numbers which has the largest sum.

Input:

−2 1 −3 4 −1 2 1 −5 4

Output:

6

which is the sum of 4 -1 2 1.

Kadane's algorithm

Time complexity: O(n)

python:

def max_subarray(A):
    max_ending_here = 0
    max_so_far = 0
    
    for x in A:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)

    return max_so_far

C++:

int max_subarray(int *A, const int len) {
	int max_ending_here = 0;
	int max_so_far = 0;

	for (int i=0; i<len; i++) {
		max_ending_here = max(0, max_ending_here + A[i]);
		max_so_far = max(max_so_far, max_ending_here);
	}

	return max_so_far;
}

---

A variation of the problem that does not allow zero-length subarrays to be returned in the case that the entire array consists of negative numbers can be solved with the following code:

def max_subarray(A):
    max_ending_here = max_so_far = A[0]
    for x in A[1:]:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

##References:

1. Wikipedia