 Here, I describe variants of Kadane’s algorithm to solve the maximum subarray and the minimum subarray problems. The maximum subarray problem is to find the contiguous subarray having the largest sum. Likewise, the minimum subarray problem is to find the contiguous subarray having the smallest sum. Variants of Kadane’s algorithm can solve these problems in O(N) time.

Kadane’s algorithm uses the dynamic programming approach to find the maximum (minimum) subarray ending at each position from the maximum (minimum) subarray ending at the previous position.

Pseudocode of Kadane’s algorithm for the Maximum subarray problem:

Pseudocode of Kadane’s algorithm for the Minimum subarray problem:

Take a look at the C++ implementation.

Try your hand at problem HOTELS, which uses this idea.

## 5 thoughts on “Kadane’s Algorithm”

1. Ashish Aggarwal says:

What about the case when all numbers are negative??

• kartik kukreja says:

How to handle all negative numbers would be part of the problem statement. Here, I am assuming that the largest number (least absolute value) should be returned in case of maximum-sum contiguous sub-array problem with all negative numbers. If you want 0 to be returned in case of all negative numbers, just initialize maxSum to 0.

Similarly in case of minimum-sum contiguous sub-array problem with all positive numbers, we can return the least positive number (by initializing minSum to infinity) or 0 (by initializing minSum to 0) as required by the problem statement.

2. Andriy Klyuchevskyy says:

Kartik, there’s an issue with your C++ implementation: suppose your first array element is < 0 then INT_MIN + (negative) will turn into very big positive (your sum result will overflow). You should start your sum from 0.

• kartik kukreja says:

No. You see we are always adding array elements to currentMaxSum (or currentMinSum), which start with 0 and not to sum which start with INT_MIN (or INT_MAX in case of minimum subarray problem) so this problem doesn’t arise.