# Two Kadane Algorithms for the Maximum Sum Subarray Problem
## 2 Growing Champions  
There are two simple conditions that the adjacent subsequences with the largest sum must have:  
1. A maximal adjacent subsequence cannot have a starting sub-subsequence with a negative sum. Eliminating such a starting sub-subsequence and starting over must result in a larger sum for the subsequence, so the original subsequence cannot be optimal.
2. After eliminating starting sub-subsequences with negative sums, the ensuing sub-subsequence must start non-negatively, so including it in the subsequence must increase (zeros do not affect the sum) the resulting sum. Thus, an optimal subsequence must start immediately after the elimination of starting sub-subsequences with negative sums.  
The algorithm is designed to exploit these ideas.  
The Champ step eliminates negative starts (see (a) above) and then begins immediately (see (b) above).  
Suppose the algorithm reports \(S\) as the largest sum among contiguous intervals. A user might want to know at least one starting and ending index of the interval whose sum is \(S\). Since Algorithm 1 is constructive, it can be modified to record the interval as it advances. This is implemented in Algorithm 2.  
```
MaxSoFar : = - \(\inf\) Champ : = - \(\inf\) For I = 1 to N do Champ : = X[I] + Max(0.0, Champ) MaxSoFar : = Max(MaxSoFar, Champ).
```  
**Algorithm 1** Linear algorithm based on Champ  
```
MaxSoFar : = - \(\inf\) Champ : = - \(\inf\) Start : = 1 End : = 1 Cstart : = 1 For I = 1 to N do if Champ < 0 then  Cstart : = I  Champ : = X[I]  else  Champ : = X[I] + Champ if MaxSoFar < Champ Start : = Cstart End : = I  MaxSoFar : = Champ.
```  
**Algorithm 2** Algorithm 1 modified to report the start and end of the first interval whose sum is maximum  
The sum \(S=\text{MaxSoFar}(\text{N})\) is unique, but the Start and End values are not. As the algorithm is written, the Start and End values are those that pertain to the first subarray whose sum is \(S\).  
A user might want to know even more: the start and end of every interval whose sum is maximum. This might be inadvisable. For example, if the input vector is all zeros, the required storage for all possible optimal intervals is of order \(n^{2}\).  
How do we know that Algorithm 1 (2) is correct? Every interval satisfying (a) and (b) is offered to MaxSoFar. Since the optimal interval must satisfy (a) and (b), the value of MaxSoFar after step \(N\) is optimal.  
These algorithms were designed with the thought that the input vector would include both positive and negative elements. If the input is entirely positive, then the optimal contiguous sequence is the entire input, and the sum of the input is the optimal sum. However, what happens with an entirely negative input? There are two possible kinds of answer a user might desire. The first is the largest of the input numbers (smallest in absolute value). Algorithms 1 and 2 deliver this result without change. The second kind of answer a user might want is the empty set. This can be offered by adding a line at the end of those algorithms (outside the loop) to report the empty set (designated however one wishes) if BestSoFar(N) is negative.