Kadane’s Algorithm

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.

Advertisements

5 thoughts on “Kadane’s Algorithm

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

    • 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. 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s