Max Contiguous Subarrays and Kadane's Algorithm

Illuminating Algorithms with print()

Posted by on November 1, 2015

Recently, I've been going through problems on HackerRank and I came across an algorithm that I couldn't quite nail down, and it bugged me. The problem I am referring to is the Maximum Subarray Problem and the algorithm used to solve it is Kadane's Algorithm. HackerRank provides a video which lays out the algorithm nicely in Python, but after staring at it for a while, I still didn't get get exactly how the algorithm was working. Maybe I needed another perspective or to see someone go through the iterations the algorithm to understand the logic more clearly. So I decided to hit up YouTube.

YouTubing It

Did I find videos on YouTube? Yes, many. Did they help? Not really, probably for multiple reasons. It is hard to explain something complex as if you are a beginner. That is, I was sure that once I understood the algorithm, the videos would be crystal clear, but they weren't doing much to help me get over the divide between having a foggy understanding and a clear understanding. But I also realized I would have to do more heavy lifting than just watching someone go through it, so I decided to bite the bullet and just revisit the original algorithm, meticulously stepping through it detail by detail.

Clarity, thy name is print

A long time ago, I found it extremely helpful to program my own algorithms on my TI to use for math exams. Programming the algorithms actually made using the TI redundant (well, not exactly redundant, they were still really convenient), because in breaking down an algorithm enough to program it, I had to learn it pretty well. Computers are "dumb," so you have to be explicit in your instructions and therefore clear in your understanding. But I already had the algorithm I needed in front of me and did not want to reinvent the wheel. I was also reluctant to dryly trek through the steps by hand. So I decided to build a "mouth-piece" for my algorithm so it could tell me what it was doing and why. Enter the print() statement.

print("what and why")

Through strategic print statements, I turned my (well, not mine) algorithm into the most efficient instructor. It would spit out what it was doing and why in a nice human-friendly format as it did it's work. Again, the process of updating the algorithm was really illuminating, but once the print statements were polished and in place, the algorithm became really clear, and I could also watch it work on many different arrays.

Here is a link to my script that explains Kadane's Algorithm step by step for you to try it yourself. You can run it in your IDE of choice by just pressing play, or you can download it and run it from the command line, and follow the printed output.

To the future

I may not see or need to use Kadane's algorithm for a while after this and because of this, I will eventually forget it. And if I ever need it, I would have to relearn probably almost from scratch. But now I can tuck my new algorithmic teacher algorithm in a repository somewhere and bust it out for an almost instant understanding of Kadane's Algorithm should I ever want or need it. Also, I hope that anyone else wanting to understand the algorithm quickly and easily could use this algorithm teacher algorithm. Actually this worked so well for me I think I'm going to make a little library of these, so hit me up if you have any requests.

Commandline Example

neil@neil-H61MLC:~$ python3 max_subarray.py
Let's find the subarray of [-6, 7, -2, 2, 4, -4, -13, 14, 8, -15] with the maximum sum using Kadane's Algorithm
Note that the first array value is at the zeroth index, not the first index
We'll think of our starting subarray as empty with sum 0
----------------

--> checking array at index 0: -6
step 1. Calculate (new value) = (current sum: 0) + (array[0]: -6) = -6
step 2. Check if (new value) > 0:
  it isn't, so we set current sum to 0 and move onto the next array value
result: our subarray so far is [] with sum 0:
----------------

--> checking array at index 1: 7
step 1. Calculate (new value) = (current sum: 0) + (array[1]: 7) = 7
step 2. Check if (new value) > 0:
  it is, so check if (current sum) = 0:
    it is, so set subarray starting index to current index 1
  since (new value: 7) > 0, (current sum: 0) is set to (new value)
step 3. Check if (current sum) > (best sum)
  (current sum: 7) > (best sum: 0), so best sum becomes: 7, best start index: 1, and best end index: 1
result: our subarray so far is [7] with sum 7:
----------------

--> checking array at index 2: -2
step 1. Calculate (new value) = (current sum: 7) + (array[2]: -2) = 5
step 2. Check if (new value) > 0:
  it is, so check if (current sum) = 0:
    it isn't, so don't change the starting index
  since (new value: 5) > 0, (current sum: 7) is set to (new value)
step 3. Check if (current sum) > (best sum)
  (current sum: 5) =< (best sum: 7), so we move on to the next array value
result: our subarray so far is [7] with sum 7:
----------------

--> checking array at index 3: 2
step 1. Calculate (new value) = (current sum: 5) + (array[3]: 2) = 7
step 2. Check if (new value) > 0:
  it is, so check if (current sum) = 0:
    it isn't, so don't change the starting index
  since (new value: 7) > 0, (current sum: 5) is set to (new value)
step 3. Check if (current sum) > (best sum)
  (current sum: 7) =< (best sum: 7), so we move on to the next array value
result: our subarray so far is [7] with sum 7:
----------------

--> checking array at index 4: 4
step 1. Calculate (new value) = (current sum: 7) + (array[4]: 4) = 11
step 2. Check if (new value) > 0:
  it is, so check if (current sum) = 0:
    it isn't, so don't change the starting index
  since (new value: 11) > 0, (current sum: 7) is set to (new value)
step 3. Check if (current sum) > (best sum)
  (current sum: 11) > (best sum: 7), so best sum becomes: 11, best start index: 1, and best end index: 4
result: our subarray so far is [7, -2, 2, 4] with sum 11:
----------------

--> checking array at index 5: -4
step 1. Calculate (new value) = (current sum: 11) + (array[5]: -4) = 7
step 2. Check if (new value) > 0:
  it is, so check if (current sum) = 0:
    it isn't, so don't change the starting index
  since (new value: 7) > 0, (current sum: 11) is set to (new value)
step 3. Check if (current sum) > (best sum)
  (current sum: 7) =< (best sum: 11), so we move on to the next array value
result: our subarray so far is [7, -2, 2, 4] with sum 11:
----------------

--> checking array at index 6: -13
step 1. Calculate (new value) = (current sum: 7) + (array[6]: -13) = -6
step 2. Check if (new value) > 0:
  it isn't, so we set current sum to 0 and move onto the next array value
result: our subarray so far is [7, -2, 2, 4] with sum 11:
----------------

--> checking array at index 7: 14
step 1. Calculate (new value) = (current sum: 0) + (array[7]: 14) = 14
step 2. Check if (new value) > 0:
  it is, so check if (current sum) = 0:
    it is, so set subarray starting index to current index 7
  since (new value: 14) > 0, (current sum: 0) is set to (new value)
step 3. Check if (current sum) > (best sum)
  (current sum: 14) > (best sum: 11), so best sum becomes: 14, best start index: 7, and best end index: 7
result: our subarray so far is [14] with sum 14:
----------------

--> checking array at index 8: 8
step 1. Calculate (new value) = (current sum: 14) + (array[8]: 8) = 22
step 2. Check if (new value) > 0:
  it is, so check if (current sum) = 0:
    it isn't, so don't change the starting index
  since (new value: 22) > 0, (current sum: 14) is set to (new value)
step 3. Check if (current sum) > (best sum)
  (current sum: 22) > (best sum: 14), so best sum becomes: 22, best start index: 7, and best end index: 8
result: our subarray so far is [14, 8] with sum 22:
----------------

--> checking array at index 9: -15
step 1. Calculate (new value) = (current sum: 22) + (array[9]: -15) = 7
step 2. Check if (new value) > 0:
  it is, so check if (current sum) = 0:
    it isn't, so don't change the starting index
  since (new value: 7) > 0, (current sum: 22) is set to (new value)
step 3. Check if (current sum) > (best sum)
  (current sum: 7) =< (best sum: 22), so we move on to the next array value
result: our subarray so far is [14, 8] with sum 22:
----------------

Finally, our max sum contiguous subarray from array [-6, 7, -2, 2, 4, -4, -13, 14, 8, -15] is [14, 8] with sum 22
'All done'

Maximum Contiguous Subarray Problem O(n) (Python)