Maximum Product Subarray

1. The obvious way

   Compute the product of every sub-list: O(n²).

2. The key insight

   At each number the new biggest product is the best of: the number alone, biggest x number, smallest x number. The new smallest is the worst of the same three. A negative number swaps the roles of biggest and smallest, which taking the max and min of all three handles automatically. A zero resets both.

3. The algorithm
   1. Biggest = smallest = answer = the first number.
   2. For each next number: candidates = (the number, biggest x number, smallest x number).
   3. New biggest = max of candidates; new smallest = min of candidates (use the OLD values).
   4. Answer = max(answer, biggest).

Watch it run

biggest 2, smallest 2, answer 2

def max_product(nums):
    biggest = smallest = answer = nums[0]
    for number in nums[1:]:
        candidates = (number, biggest * number, smallest * number)
        biggest, smallest = max(candidates), min(candidates)
        answer = max(answer, biggest)
    return answer

Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.