Maximum subarray problem: Difference between revisions

Revision as of 23:19, 27 February 2023

Revision as of 15:08, 28 February 2023

Line 2:

[[File:Maximum Subarray Visualization.svg|thumbnail|Visualization of how sub-arrays change based on start and end positions of a sample. Each possible contiguous sub-array is represented by a point on a colored line. That point's y-coordinate represents the sum of the sample. Its x-coordinate represents the end of the sample, and the leftmost point on that colored line represents the start of the sample. In this case, the array from which samples are taken is [2, 3, -1, -20, 5, 10]. ]]

In [[computer science]], the '''maximum sum subarray problem''', also known as the '''maximum segment sum problem''', is the task of finding a contiguous subarray with the largest sum, within a given one-dimensional [[array data structure|array]] A[1...n] of numbers. It can be solved in <math>O(n)</math> time and <math>O(1)</math> space.

Formally, the task is to find indices <math>i</math> and <math>j</math> with <math>1 \leq i \leq j \leq n </math>, such that the sum

Line 15:

# Several different sub-arrays may have the same maximum sum.

Although this problem can be solved using several different algorithmic techniques, including brute force,{{sfn|Bentley|1989|p=70}} divide and conquer,{{sfn|Bentley|1989|p=73}} dynamic programming,{{sfn|Bentley|1989|p=74}} and reduction to shortest paths, a simple single-pass algorithm known as Kadane's algorithm solves it in <math>O(n)</math> time and <math>O(1)</math> spaceefficiently.

== History ==