DSA sheet · Arrays · Kadane's Algorithm pattern

Maximum Product Subarray

The second question of the Kadane's section. It looks like Maximum Subarray with × instead of +, but the sign of a product can flip: one negative makes a product negative, a second negative makes it positive again. The teacher writes the brute force first (all subarrays, keep the biggest product), then checks her four patterns and finds that two of them could work. She explains why the plain Kadane's rule "drop it when it goes negative" breaks for products, says the Kadane's fix is a small "state DP" that she will cover in a later video, and solves it here with a prefix and suffix product scan, including how to handle zeros.

Why it matters: a very negative product today can become the biggest product tomorrow, as soon as one more negative number arrives. Learning to keep that in mind (either by scanning from both ends, or by tracking the smallest product too) is the key idea here.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting (subarrays, Kadane's, signs and zeros from scratch)
• Part A · Brute force: multiply out every subarray
• Part B · Optimal (the teacher's way): prefix and suffix products
• Part C · The Kadane's way: track the max AND the min (the "state DP" she promises)
• Part D · Revision page

Part 0 · Before starting

What is a subarray?

A subarray is a piece of the array whose elements sit next to each other (contiguous): a start index, an end index, and everything in between, with nothing skipped. Its product is all its elements multiplied together.

The brute force over all subarrays

Fix a start i, then move an end j from i to the last index, multiplying one more element into a running product each time. That visits all n·(n+1)/2 subarrays, so it is O(n²), and it redoes nearly the same multiplications for every start.

Kadane's idea for sums (from the previous problem)

For the maximum sum, we walk once and keep a running sum. At every index the best subarray ending there either extends the previous one or starts fresh. Extending is only worth it if the past total is positive, so the rule is: add the number, record the best, and if the running sum is negative, reset it to 0. That's safe because a stretch with a negative sum can only lower any subarray that includes it, so the best subarray never begins with one. For an all-negative array, the best must be the largest single number, so the best starts at nums[0] (never 0) and is recorded before each reset.

Why products are different: the sign flips

• positive × positive = positive · positive × negative = negative · negative × negative = positive.
• So a product that is very negative right now is not "bad". If another negative comes later, it turns into a very large positive.
• That's why "throw it away when it goes negative" (the sum rule) is wrong for products. The teacher's example: [−2, 3, 4, −1]. Dropping −2 at once, then 3 × 4 = 12, then dropping −1, gives 12. But all four together give (−2)·3·4·(−1) = 24.
• When a negative appears, you don't yet know whether keeping it will pay off. That depends on whether another negative comes later. So we keep two possibilities alive. There are two standard ways:
  • Track both the max and the min product ending here (Kadane's with two states). The min is the "most negative" one, which a later negative can flip into the max. The teacher calls this a state DP (keep both "took it" and "didn't take it" alive) and leaves it for a later video. Part C shows it.
  • Prefix and suffix scan: multiply from the left and from the right, and take the best product seen in either scan. This is what the teacher teaches in this video (Part B).

Zeros reset everything

Anything times 0 is 0, and it stays 0 forever after. A subarray that crosses a zero has product 0, so a zero splits the array into separate pieces. Once a running product hits 0, we record that 0 (it can be the answer, e.g. [−2, 0, −1] → 0) and then restart the product at 1 on the other side.

How this relates to sliding window, and why a plain window fails

Sliding window grows the window with right and shrinks it with left. That needs a monotonic rule. For example, with positive numbers ≥ 1, a product only grows when you add an element and only drops when you remove one. Then "grow until invalid, then shrink" is safe (that's how Subarray Product Less Than K works).

Here negatives break that. Adding −2 can turn a huge positive into a huge negative, and adding another −1 turns it back. There is no "valid / invalid" condition to grow and shrink by, and moving left one step can raise or lower the product depending on the sign. The teacher rules sliding window out for exactly this reason: it needs all numbers positive.

The teacher's 4 array patterns, checked for this problem

Part A · Brute force: multiply out every subarray

LeetCode 152

1The question in simple words

You get an integer array nums. Find the (non-empty) subarray whose product is the largest, and return that product.

2What the constraints tell us

• The answer fits in a 32-bit integer (LeetCode promises this). The teacher's point: multiplying many numbers can easily get huge, and normally you'd reach for a long. Here the tests are built so an int is enough. (In Python ints never overflow, so we don't worry about it at all.)
• 1 ≤ n ≤ 2·10⁴. O(n²) is about 4·10⁸, past the ~10⁸ comfort line. It will be very slow or TLE, so we should optimise.
• −10 ≤ nums[i] ≤ 10. Numbers can be negative (and can be 0). That decides the pattern: one negative makes the product negative, two negatives make it positive again.

3Intuition: list every subarray, keep the biggest product

If you know how to generate all subarrays, the problem is easy. Stand at start i, let j walk to the end, and multiply nums[j] into a running product. Each step gives the product of [i..j]. Compare it with the best so far.

4Building the logic from the example

nums = [2, 3, −2, 4]:

• i = 0: [2] → 2 · [2, 3] → 6 · [2, 3, −2] → −12 · [2, 3, −2, 4] → −48.
• i = 1: [3] → 3 · [3, −2] → −6 · [3, −2, 4] → −24.
• i = 2: [−2] → −2 · [−2, 4] → −8.
• i = 3: [4] → 4.

The biggest is 6.

The running product starts at 1, not 0

For a sum we start at 0, because adding 0 changes nothing. For a product, starting at 0 would make every product 0. The "do nothing" value for multiplication is 1, so prod = 1 for each new start.

What should the best answer start as?

The teacher weighs 0, −1, −∞ and −10:

• 0 or −1 are not safe. If the array is just [−10], the answer is −10, but a start of 0 or −1 would never be replaced.
• −∞ is safe: any real product beats it.
• −10 is also safe, and more precise: the smallest allowed number is −10, so the answer (which is at least as big as the largest single element) can never be below −10. With [−10] alone, −10 is exactly right. With [−10, −10], the product 100 simply replaces it.

5Approach steps

1. max_prod = -10 (or −∞).
2. For each start i: prod = 1.
3. For each end j from i: prod *= nums[j], then max_prod = max(max_prod, prod).
4. Return max_prod.

6Code (Python)

class Solution:
    def maxProduct(self, nums):
        n = len(nums)
        max_prod = -10                    # smallest possible answer (or float('-inf'))
        for i in range(n):                # start of the subarray
            prod = 1                      # 1, not 0: the neutral value for *
            for j in range(i, n):         # end of the subarray
                prod *= nums[j]           # prod = product of nums[i..j]
                max_prod = max(max_prod, prod)
        return max_prod

7Code line by line

8Dry run (hand table)

Final answer: 6 ✓.

9Complexity & remember

• Time O(n²): the inner loop runs about n, then n − 1, then n − 2, … times, so about n²/2 in total. For n = 2·10⁴ that's ~2·10⁸ multiplications. The teacher's submission was accepted but very slow. (In Python this is likely to TLE.)
• Space O(1).

Part B · Optimal (the teacher's way): prefix and suffix products

LeetCode 152

1The question again, with the new goal

Same question, in O(n): one pass, no restarting from every index.

2Why not just copy Kadane's from the sum problem?

The teacher tries the plain Kadane's rule on [−2, 3, 4, −1]:

• −2 is negative → drop it. Start again at 3.
• 3 × 4 = 12.
• × (−1) = −12, negative → drop it. Answer 12?

But taking all four gives (−2)·3·4·(−1) = 24, which is far bigger. The two negatives cancel. And if the last −1 weren't there, keeping −2 would have been a mistake ([−2, 3, 4] = −24 < 12). So when you meet a negative, you can't decide yet whether to keep it. You'd need to carry both options forward ("took it" and "didn't take it"). That is the state-DP version of Kadane's, which she defers. (It's written out in Part C.) Here she uses the other pattern that fits: prefix and suffix.

3Intuition: multiply from the left, and from the right

• Prefix scan: walk left → right, multiplying as you go. After each step you have the product of a subarray that starts at the left edge. Record the best.
• Suffix scan: walk right → left the same way. Now each product is a subarray that ends at the right edge. Record the best.
• The answer is the best product seen in either scan.

Why should the best subarray always touch one of the edges? Because with whole numbers, multiplying in more non-zero elements never makes the size (absolute value) of the product smaller. Only the sign can go wrong. If the count of negatives is even, the whole stretch is positive and is the biggest. If it's odd, we must leave out one negative, together with everything on one side of it. The best way is to cut off the first negative and everything before it (that's a suffix), or the last negative and everything after it (that's a prefix). One of the two scans finds it.

4Building the logic from examples

Example 1: [2, 3, −2, 4]: the prefix scan alone works

Left → right: 2 (best 2), 6 (best 6), −12, −48. Best = 6. That is the answer.

Example 2: add one more number, [2, 3, −2, 4, 2]: the prefix scan misses it

Left → right: 2, 6, −12, −48, −96. Best from the left is still 6. But [4, 2] = 8 is bigger. The prefix scan never sees it, because it is stuck carrying the −2. So the teacher runs a second scan from the right end: 2, 2·4 = 8, then × (−2) = −16, × 3 = −48, × 2 = −96. Best from the right = 8. Answer = max(6, 8) = 8 ✓.

Example 3: a zero in the middle, [2, 3, −2, 4, 0, 2, 4]

Left → right: 2, 6, −12, −48, then × 0 = 0. From here every product would be 0 forever (0 × 2, 0 × 4, …). We don't want to carry the zero. So whenever the product becomes 0, we start again from 1: 1 × 2 = 2, then × 4 = 8. The suffix side does the same: from the right, 4, 8, then × 0 = 0 → restart at 1 → 1 × 4 = 4, and so on. Both scans find 8.

One loop instead of two: the index n − i − 1

We could write two loops (left → right, then right → left), which is O(2n). The teacher merges them into one: at step i, the prefix multiplies nums[i] and the suffix multiplies the element at the mirror position from the end. With n = 4: when i = 0 the suffix needs index 3; i = 1 → 2; i = 2 → 1; i = 3 → 0. The formula is n − i − 1: 4 − 0 − 1 = 3, 4 − 1 − 1 = 2, and so on.

5Approach steps

1. prefix = 1, suffix = 1 (1, not 0, because we multiply), ans = −∞ (or −10).
2. For each i from 0 to n − 1:
3. If prefix == 0, set it back to 1. Same for suffix. (A zero was just passed.)
4. prefix *= nums[i], suffix *= nums[n − i − 1].
5. ans = max(ans, prefix, suffix).
6. Return ans.

6Code (Python)

class Solution:
    def maxProduct(self, nums):
        n = len(nums)
        prefix = 1                        # product from the left edge (or since the last 0)
        suffix = 1                        # product from the right edge (or since the last 0)
        ans = float('-inf')               # -10 also works
        for i in range(n):
            if prefix == 0:               # we crossed a zero: start again
                prefix = 1
            if suffix == 0:
                suffix = 1
            prefix *= nums[i]             # left -> right
            suffix *= nums[n - i - 1]     # right -> left, at the same time
            ans = max(ans, prefix, suffix)
        return ans

7Code line by line

8Dry run

Run 1: nums = [2, 3, −2, 4, 2] (n = 5)

Answer 8 ✓ ([4, 2]). The prefix alone would have stopped at 6.

Run 2: nums = [2, 3, −2, 4, 0, 2, 4] (n = 7), with a zero

The prefix scan at its key moments (yellow = the current prefix product, grey = left behind by a zero reset):

Answer 8 ✓.

9Complexity & remember

• Time O(n): one loop that does two multiplications per step. Two separate loops would be O(2n), still linear, but one loop is neater.
• Space O(1): three variables.

She submitted it and it beat about 90%: "the fastest solution" for this problem.

Part C · The Kadane's way: track the max AND the min

This is the "state DP" version of Kadane's that the teacher mentions and leaves for a later video. It is not coded in this video. It is written here so the page is complete, and you'll meet it again.

1The question

The same as Part A. We want one pass, in Kadane's style.

2Constraints

The same as Part A. Negatives and zeros are allowed, and n is up to 2·10⁴, so O(n) is the goal.

3Intuition: keep two runs alive

For sums, one number was enough: the best sum ending here. For products, we keep two:

• cur_max: the largest product of a subarray ending at this index;
• cur_min: the smallest (most negative) product of a subarray ending at this index.

When the next number x is negative, the roles swap: the smallest product times x becomes the largest, and the largest times x becomes the smallest. That's the teacher's "took it / didn't take it" idea. The very negative run is kept as cur_min in case a later negative flips it.

4Building the logic

At each index, the best subarray ending here is one of three things: x alone (start fresh), cur_max × x (extend the biggest), or cur_min × x (extend the smallest, which wins when x < 0). So:

• new_max = max(x, cur_max·x, cur_min·x)
• new_min = min(x, cur_max·x, cur_min·x)

A common shortcut: if x < 0, swap cur_max and cur_min first. Then cur_max = max(x, cur_max·x) and cur_min = min(x, cur_min·x).

5Approach steps

1. cur_max = cur_min = ans = nums[0].
2. For each next number x: if x < 0, swap cur_max and cur_min.
3. cur_max = max(x, cur_max·x), cur_min = min(x, cur_min·x).
4. ans = max(ans, cur_max). Return ans at the end.

6Code (Python)

class Solution:
    def maxProduct(self, nums):
        cur_max = cur_min = ans = nums[0]
        for x in nums[1:]:
            if x < 0:                         # a negative flips big and small
                cur_max, cur_min = cur_min, cur_max
            cur_max = max(x, cur_max * x)     # start fresh, or extend
            cur_min = min(x, cur_min * x)
            ans = max(ans, cur_max)
        return ans

7Code line by line

8Dry run on the teacher's [−2, 3, 4, −1]

Answer 24 ✓, the same answer the prefix scan gives (its prefix after four steps is 24).

9Complexity & remember

• Time O(n), Space O(1), the same as Part B.

Part D · Revision page

s = Solution()
print(s.maxProduct([2, 3, -2, 4]))            # 6
print(s.maxProduct([-2, 0, -1]))              # 0
print(s.maxProduct([2, 3, -2, 4, 2]))         # 8  (needs the suffix scan)
print(s.maxProduct([-2, 3, 4, -1]))           # 24 (two negatives cancel)
print(s.maxProduct([2, 3, -2, 4, 0, 2, 4]))   # 8  (zero reset)
print(s.maxProduct([-3]))                     # -3 (single element)
print(s.maxProduct([-2, -3, -4]))             # 12 (odd count of negatives)

Based on this video: Maximum Product Subarray | Prefix & Suffix