Maximum subarray problem: Difference between revisions

Revision as of 03:03, 26 February 2023

Revision as of 22:36, 27 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.

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

: <math>\sum_{x=i}^j A[x] </math>

is as large as possible. (Some formulations of the problem also allow the empty subarray to be considered; by convention, [[empty sum|the sum of all values of the empty subarray]] is zero.) Each number in the input array A could be positive, negative, or zero.{{sfn|Bentley|1989|p=69}}

Line 13 ⟶ 15:

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

ThisAlthough 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.{{cn|date=October, 2019}}a simple single-pass algorithm known as Kadane's algorithm solves it in <math>O(n)</math> time and <math>O(1)</math> space.

== History ==