maximum subarray problem

The problem of finding the contiguous stretch of an array whose values have the largest sum.

In more detail

Brute force checks every start and end pair in O(n^2). Divide and conquer splits the array, solves each half and checks the best subarray crossing the middle, for O(n log n). A linear-time dynamic-programming solution, Kadane's algorithm, also exists.

Related terms

Taught in

References