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.

28.635308
77.224960

### Like this:

Like Loading...

*Related*

Pingback: Preparing for the Coding Interview | Everything Under The Sun

What about the case when all numbers are negative??

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.

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.

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.