# Two Kadane Algorithms for the Maximum Sum Subarray Problem
## 3 The Linear Algorithm Bentley Gave Me Credit for  
This algorithm recursively calculates \"BestEndingHere\" at each stage. Formally, it looks like this:  
As in Algorithm 1, Algorithm 3 honors (a) by restarting in MaxEndingHere, and (b) by restarting immediately.  
```
MaxSoFar := 0.0 MaxEndingHere := 0.0 for I = 1 to N do MaxEndingHere :=Max(0.0, MaxEndingHere + X[I]) MaxSoFar := Max(MaxSoFar, MaxEndingHere).
```  
**Algorithm 3** Same as Algorithm 4 in Bentley [5]  
The next question is whether Algorithm 3 can be modified to give the start and end positions of an optimal subsequence. The following algorithm does that.  
```
MaxSoFar := 0.0 MaxEndingHere := 0.0 Start := 1 End := 1 Mstart := 1 for I = 1 to N do if MaxEndingHere + X[I] < 0.0 then  Mstart := I MaxEndingHere := 0.0 else MaxEndHere := MaxEndhere + X[I] if MaxSoFar < MaxEndingHere then  MaxSoFar := MaxEndingHere  Start = Mstart End = I.
```  
**Algorithm 4** Algorithm 3 modified to report the start and end of an optimal subsequence  
The correctness of Algorithm 3 can be seen by induction. If MaxEndingHere at I-1 is correct, then so is MaxEndingHere at I.  
An input vector that has only negative numbers leads, using Algorithm 3, to a MaxSoFar of zero, and the empty set. In this particular, it differs in behavior from Algorithm 1. A result of 0 could also occur if the input is non-positive and includes at least one 0. Hence, an Algorithm 3 result of 0 is ambiguous.  
Is this algorithm merely a toy? No, it has been used in applications. Its origin came from efforts to find two-dimensional regions of high response in images [5]. The two-dimensional case is substantially more difficult than the one-dimensional case because the input is not simply ordered. Nonetheless, some of the algorithms proposed for the two-dimensional case use Algorithm 3 as a subroutine [6; 7; 8; 9]. The time complexity of these algorithms for an \(r\times c\) input is \([min(r,c)]^{2}+max(r,c)\). An application of these methods to optical and radio astronomy is given in [10]. Of course there are analogous problems for arrays of arbitrary dimensions, but one has to expect algorithms to be slower and demand more memory as the dimensions increase.  
The algorithm is also used in computational biology, for example, in [11; 12; 13]. These applications make use of the linear speed on long DNA chains.  
Additionally, electrical bio-engineers have found it useful. The \(R\)-peak is one of the parameters used in the analysis of electrocardiogram (ECG) data. In a study of a prototype of a wearable ECG system, [PERSON] et al. [14] use a modification of the algorithm to capture and compress \(R\)-peak data.  
Computer scientists have used the algorithm to explore string matching, which has many uses [15].  
While these applications show that the algorithm is useful in certain problems, such applications are only part of the story. What explains that Leetcode has had 6.9 million downloads of the maximum subarray problem [16]?  
The first answer, I believe, is its widespread use as an interview question for coders seeking employment. Leetcode introduces themselves as \"the best platform to help you advance your skills, expand your knowledge and prepare for technical interviews.\" Why would this be an attractive question to test a candidate voter? The problem is easy to state. The algorithm is simple to code, if the candidate understands it. Additionally, there are various ways of disguising it, such as proposing an array of positive numbers, and asking for the subarray with the largest product.  
There is a second answer as well. The algorithm is an application of dynamic programming. For teaching purposes, it can be introduced as a simple example of dynamic programming, a powerful method when it applies [17].