Neetcode - Maximum Product Subarray

Read the error, not the panic.

Today, we're going to solve this interesting problem, which is clearly related to dynamic programming (DP). I’ve tackled it before using Python, but this time I approached it with C++, and still learned a lot from revisiting this "old friend." The following is my working solution—though I initially had a bug with the outer loop boundary. That said, this version can be further optimized, and we’ll walk through both the current and the optimized solutions together.

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int max_prod = INT_MIN;

        dfs(1, max_prod, nums);

        return max_prod;
    }
    
    void dfs(int len, int& max_prod, vector<int>& nums) {
        int n = nums.size();
        if (len > n) return;

        for (int i = 0; i <= n - len; ++i) {
            int prod = 1;
            for (int j = i; j < i + len; ++j) {
                prod *= nums[j];
            }
            max_prod = max(max_prod, prod);
        }

        dfs(len + 1, max_prod, nums);
    }
};

This solution uses a recursive approach that gradually increases the window size until there are no more elements to process. However, you can observe that this is essentially a brute-force method that explores all possible subarrays. To improve efficiency, we apply Kadane’s Algorithm, which we will introduce first.

Kadane's Algorithm

This algorithm answers the question: “At each index, is it better to continue the current subarray or start a new one from this index?” The key insight behind the code is:

A maximum subarray ending at index k has two choices:

1. Extend the previous subarray (keep what we have)
2. Drop everything and start a new subarray from index k

Take [-2, 3, -1, 5, -3] as an example. Starting from index 0:

• Index 0
  • Take -2
  • current_sum = -2, max_sum = -2
• Index 1: Is it better to continue from -2 → 3 or start fresh from 3?
  • Continue: -2 + 3 = 1
  • Restart: 3
  • Choose the better: current_sum = max(1, 3) = 3, max_sum = max(-2, 3) = 3
• Index 2: Continue from 3 → -1 or restart from -1?
  • Continue: 3 + (-1) = 2
  • Restart: -1
  • current_sum = max(2, -1) = 2, max_sum = max(3, 2) = 3

In brief, Kadane’s algorithm teaches us to decide at each step whether to take the current element or start fresh from it. This classic greedy approach leads to an optimal solution for the maximum subarray problem. However, it’s important to note that greedy methods don’t always guarantee optimal solutions in every problem. Here is the code:

class SolutionKadane {
public:
  int maxProduct(vector<int>& nums) {
    int max_prod = nums[0];
    int cur_min = 1, cur_max = 1;

    for (int num : nums) {
      int val = num * cur_max;
      cur_max = max(max(num * cur_max, num * cur_min), num);
      cur_min = min(min(val, num * cur_min), num);
      max_prod = max(max_prod, cur_max);
    }

    return max_prod;
  }
}

I would also like to present the prefix and suffix approach. This solution computes a prefix product starting from the beginning of the array moving right, and a suffix product starting from the end of the array moving left. At each step, it updates the maximum product encountered among all prefix and suffix products seen so far.

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        int max_prod = nums[0];

        int prefix = 0, suffix = 0;
        for (int i = 0; i < n; ++i) {
            prefix = nums[i] * (prefix == 0 ? 1 : prefix);
            suffix = nums[n - 1 - i] * (suffix == 0 ? 1 : suffix);
            max_prod = max(max_prod, max(prefix, suffix));
        }
        return max_prod;
    }
};

This solution works because of the continuity property. I was a bit surprised by how this property relates to the maximum subarray product problem.

Conclusion

In brief, I was only able to meet the baseline requirements for this question and couldn’t devise a more efficient solution in terms of time complexity. However, this exercise served as a valuable review of both C++ syntax and dynamic programming concepts.