LeetCode 30-Day Challenge: Wrekt On Day Three By Maximum Subarray

C++: Practice

Because of the stay-at-home orders being handed down across the globe, LeetCode launched a 30-day programming challenge for April. I am under no illusion that I'll ever write solutions for LeetCode problems that can compete with some of the geniuses out there. I've always admired the people who can write cryptic one-liners that solve a problem with magical time-space complexity (even though these solutions are often impractical in production). I can, however, at least hold my own and get the problem solved, hopefully in a clean, easy-to-reason-on manner.

That all fell apart today, day #3. We were presented with finding the contiguous subarray of an array that has the largest sum. The notes made me happy.

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

I love divide & conquer (probably because I love recursion). I knew if I just split the array in half the algorithm would miss subarrays that contained portions of both halves. I cooked up this approach that totals the array, then it splits it up into two parts, the left is one element short of the end and the right element is one element short of the beginning.

Slow As Molasses

My first approach got destroyed by the following test case.

-84,-87,-78,-16,-94,-36,-87,-93,-50,-22,-63,-28,-91,-60,-64,-27,-41,-27,-73,-37,-12,-69,-68,-30,-83,-31,-63,-24,-68,-36,-30,-3,-23,-59,-70,-68,-94,-57,-12,-43,-30,-74,-22,-20,-85,-38,-99,-25,-16,-71,-14,-27,-92,-81,-57,-74,-63,-71,-97,-82,-6,-26,-85,-28,-37,-6,-47,-30,-14,-58,-25,-96,-83,-46,-15,-68,-35,-65,-44,-51,-88,-9,-77,-79,-89,-85,-4,-52,-55,-100,-33,-61,-77,-69,-40,-13,-27,-87,-95,-40

Nothing I could think of or do made it fast enough to pass. In fact, it was so slow that it never finished while I was coding up the next approach. I was determined to use divide & conquer to solve this problem, but first looked up how to solve it using dynamic programming. The answer is... less than desirable for my taste, but I understood the approach. It's called Kadane’s algorithm.

I started Googling how to solve the problem specifically with divide & conquer. Let me say, for the record, the code on GeeksforGeeks is almost always terrible and the explanations are even worse.

Then I stumbled across this gem, a paper with diagrams explaining the mathematics behind a divide & conquer approach, including pseudocode. I gave it a quick read then got to work translating the pseudocode into herbocode.

Good Writers FTW

That's a solid win for a well written technical paper! This one will go in my library of how to document an algorithm or theory effectively.