Maximum Subarray Product Performance: Divide and Conquer vs Kadane's Algorithm

Original leetcode article is here.

I recently came across this list of problems to study from to become a better programmer. This is quite a famous list in the industry and a favorite for a lot of people preparing for software engineering interviews at FAANG companies (Facebook, Amazon, Apple, Netflix and Google).

Anyhow, I ran into issues pretty much from the get-go. Some patterns were easier to learn than others (so far). However, the problem that gave me a headache since yesterday evening is this one. This is a `maximum subarray product` problem that can have an arbitrary number of elements containing 0s, negative and positive numbers. While it was relatively simple to understand the problem conceptually, it was surprisingly hard to implement a solution.

Now, my approach to solve a problem is to do it iteratively. I typically open up a Python console and type up a solution that I think should work. I then run it with a few example inputs, as varied and edgy as I can conjure, and look at the resulting errors and go from there. Once I am satisfied with the solution, I look around in the code to improve readability and reduce jumps, if possible.

Trying to do this I realised that this problem can be solved by the divide and conquer method as follows:

1. Divide the array into subarrays whenever a 0 is encountered
2. For each subarray use one pass to check for negative numbers - even or odd number of negative numbers and first and last position of those negative numbers
3. If there are an even number of negative numbers then all the numbers in the subarray can be multiplied
4. If there are odd number of negative numbers then calculate two products - one that contains the first negative number and the other that contains the last negative number. Choose the maximum of those two.
5. Finally, return the maximum of 0 and the products of all the subarrays.

I tested my solution against some of the most voted ones, listed below:

1. Python-solutions-with-different-space-costs-(O(2*n)-O(1))
2. Python-Simple-Solution-Explained-(video+code)-(91-faster)
3. Python-Easily-understandable-Solution-using-kadanes-algorithm
4. Python-solution-with-detailed-explanation

Out of three runs, my speed varied between 86.5% to 98.91% while memory usage varied between 36.87% to 85.49%. On the fastest run, my speed was better than 98.91% of the solutions submitted and memory usage on that run was 63.88% better than solutions submitted. In contrast, solution 4 - `Python-solution-with-detailed-explanation` - in the list above had a memory utilisation better than 95.37% solutions but faster than only 69.01%. Solution 2 - `Python-Simple-Solution-Explained-(video+code)-(91-faster)` - was as fast, faster than 98.91% of the solutions, but had a memory utilisation better than a meager 14.54% of the solutions.

However, my solution remains quite unreadable; maybe there is some recursive version that I have not thought of. However, I found solution 2 to be most elegant with a helpful explanation video too.

Here is my code in its entirety: