Kadane’s algorithm finds the maximum sum of a contiguous, nonempty subarray in O(n) time and O(1) extra space. The key is to decide at each element whether to extend the current subarray or start a new one.
For example, for an array, a = [-2, -4, 4, -2, -1, 1, 5, -7]
A contiguous subarray = [4, -2, -1, 1, 5] gives the maximum sum of 7.
Application
Maximum sum subarray problem finds application in many fields like finance, genomic, sequence analysis and computer vision. One of the real life example of it is to find out a part of the year the company earns more income and how much it earns. It is also useful in analysis of genomic sequence to identify important biological segments of protein sequences. In computer vision, it is used to detect the brightest area in an image. Some other applications include GC-rich regions, DNA binding domains, low-complexity filter and regions of high charge.
Solution Algorithm
Several algorithmic techniques, including brute force, divide and conquer, dynamic programming, and reduction to the shortest paths can solve this problem. However, the fastest and most efficient algorithm is for solving it is Kadane algorithm. It has a time complexity of O(n) while divide and conquer algorithm which has a time complexity of O(n.log(n)) and a straightforward brute-force method with running sums takes O(n²)
Kadane Algorithm
Kadane algorithm is the most efficient algorithm for solving Maximum Subarray Problem. It has a time complexity of O(N). Idea of Kadane algorithm is very simple and elegant. It tracks the best nonempty subarray ending at each position, including when every value is negative. Variable max_current stores the maximum value of current positive contiguous segment and max_so_far store the maximum of all the max_current.
Program
Python 3 Code
def max_subarray_sum(values):
if not values:
raise ValueError("At least one number is required")
current = best = values[0]
for value in values[1:]:
current = max(value, current + value)
best = max(best, current)
return best
values = [-2, -4, 4, -2, -1, 1, 5, -7]
print(max_subarray_sum(values)) # 7
Java Code
public class Kadane {
static long maxSubArraySum(int[] values) {
if (values == null || values.length == 0)
throw new IllegalArgumentException("Nonempty input required");
long current = values[0], best = values[0];
for (int i = 1; i < values.length; i++) {
current = Math.max((long) values[i], current + values[i]);
best = Math.max(best, current);
}
return best;
}
public static void main(String[] args) {
int[] values = {-2, -4, 4, -2, -1, 1, 5, -7};
System.out.println(maxSubArraySum(values)); // 7
}
}
C++ Code
#include <algorithm>
#include <iostream>
#include <stdexcept>
#include <vector>
using namespace std;
long long maxSubArraySum(const vector<int>& values) {
if (values.empty()) throw invalid_argument("Nonempty input required");
long long current = values[0], best = values[0];
for (size_t i = 1; i < values.size(); ++i) {
current = max(static_cast<long long>(values[i]), current + values[i]);
best = max(best, current);
}
return best;
}
int main() {
vector<int> values = {-2, -4, 4, -2, -1, 1, 5, -7};
cout << maxSubArraySum(values) << endl; // 7
}
Request
If you find a problem with the current code or some other way to do that may be useful to others please comment it or mail it to [email protected]
Updated explanation and practical examples
For [-2, -4, 4, -2, -1, 1, 5, -7], the maximum contiguous sum is 7 from [4, -2, -1, 1, 5]. Initialize current = best = numbers[0]; for x in numbers[1:], set current = max(x, current + x) and best = max(best, current). This initialization correctly handles all-negative inputs: [-5, -2, -8] returns -2. Empty arrays require an explicit policy, such as raising ValueError. The simple brute-force algorithm with running sums takes O(n²), not O(n⁶).
Frequently asked questions
Q: Does Kadane’s algorithm allow an empty subarray? A: This implementation does not; a variant that permits empty subarrays may return zero for all-negative input. Q: Can it return the subarray indexes? A: Yes, track the candidate start when restarting and update best start/end when the best sum improves. Q: Does it work for floats? A: Yes, subject to floating-point precision.
Verified edge cases and limitations
For [-5, -2, -8], the answer is -2, not zero: this tutorial requires a nonempty subarray. A single-element list returns that element. Empty input raises an error. Python integers grow as needed; the Java example accumulates in long and the C++ example uses long long, which still have finite ranges. For a different convention that permits an empty subarray, the answer for all-negative inputs may be zero.
The loop visits each element once, so time complexity is O(n) and auxiliary space is O(1), excluding the input. A naive method that recomputes each subarray sum can take O(n³); retaining a running sum within each starting position reduces brute force to O(n²). For another Python algorithm example, see bubble sort in Python.
Edge Cases, Complexity and Practical Limits
The three implementations use a nonempty subarray definition. For [-5, -2, -8] the maximum sum is -2, not zero; a one-element input returns its element, and an empty input raises an error. Each algorithm uses O(n) time and O(1) extra working space. Java accumulates in long and C++ in long long, which have finite ranges; Python integers can grow as needed. Brute-force enumeration with running sums takes O(n²), while recomputing every subarray sum from scratch takes O(n³).
C P Gupta is a YouTuber and Blogger. He is expert in Microsoft Word, Excel and PowerPoint. His YouTube channel @pickupbrain is very popular and has crossed 9.9 Million Views.