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
- divide and conquer — A problem-solving technique that splits a problem into independent smaller pieces, solves each recursively, and combines their answers.
- subarray — A contiguous run of elements within an array, such as positions 3 through 7.
- brute force — Solving a problem by trying every possibility directly, without any clever structure.
Taught in
- Divide And Conquer And The Recurrence — Algorithms & Data Structures for Working Engineers