Maximum subarray problem

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, 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 <a href="/facts/Array_data_structure/BKGvF8AM">array</a> A[1...n] of numbers. It can be solved in 
 
 
 
 O
 (
 n
 )
 
 
 {\displaystyle O(n)}
 
 time and 
 
 
 
 O
 (
 1
 )
 
 
 {\displaystyle O(1)}
 
 space.
Formally, the task is to find indices 
 
 
 
 i
 
 
 {\displaystyle i}
 
 and 
 
 
 
 j
 
 
 {\displaystyle j}
 
 with 
 
 
 
 1
 ≤
 i
 ≤
 j
 ≤
 n
 
 
 {\displaystyle 1\leq i\leq j\leq n}
 
, such that the sum

∑
          
            x
            =
            i
          
          
            j
          
        
        A
        [
        x
        ]
      
    
    {\displaystyle \sum _{x=i}^{j}A[x]}

is as large as possible. (Some formulations of the problem also allow the empty subarray to be considered; by convention, <a href="/facts/Empty_sum/bvMsoUNh">the sum of all values of the empty subarray</a> is zero.) Each number in the input array A could be positive, negative, or zero.
For example, for the array of values [−2, 1, −3, 4, −1, 2, 1, −5, 4], the contiguous subarray with the largest sum is [4, −1, 2, 1], with sum 6.
Some properties of this problem are: 

<ol><li>If the array contains all non-negative numbers, then the problem is trivial; a maximum subarray is the entire array.</li>
<li>If the array contains all non-positive numbers, then a solution is any subarray of size 1 containing the maximal value of the array (or the empty subarray, if it is permitted).</li>
<li>Several different sub-arrays may have the same maximum sum.</li></ol>
Although this problem can be solved using several different algorithmic techniques, including brute force, divide and conquer, dynamic programming, and reduction to shortest paths, a simple single-pass algorithm known as Kadane's algorithm solves it efficiently.

Maximum subarray problem open-in-new

Maximum subarray problem