LeetCode: Maximum Product Subarray

LeetCode Challenge: Maximum Product Subarray

Naive solution

The most naive approach is iterating over all the ranges of the array, and iterate elements in the range to compute a product for this range, the time complexity will be $O(N^3)$.

An optimization is using a table to store the computed result, table[i][j] means the product of range(i, j), so when we compute the result of range(i, j+1), we just need to compute the value of table[i][j] * arr[j+1] => table[i][j+1].

But the overall time complexity is still: $O(N^2)$, it will be Time Limit Exceeded.

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        vector<vector<int> > table = 
            vector<vector<int> >(nums.size(), vector<int>(nums.size(), 0));
        
        int ans = nums[0];
        for(int i=0; i < nums.size(); i++) {
            table[i][i] = nums[i];
            ans = max(nums[i], ans);
        }
        
        for(int i = 0; i < nums.size(); i++) { 
            for(int j = i+1; j < nums.size(); j++) {
                int product = table[i][j-1] * nums[j];
                table[i][j] = product;
                ans = max(ans, product);
            }
        }
        return ans;
        
    }
};

Approach of linear scan

Similar with previous challenge of maximum subarray. The difference is we need to save both current minimum and maximum product, because if current element is less then zero, minimum maybe also a negative value, the product of them maybe the next maximum.

The time complexity is: $O(N)$.

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int cur_min = nums[0];
        int cur_max = nums[0];
        int ans = nums[0];
        
        for(int i=1; i < nums.size(); i++) {
            if(nums[i] < 0) 
                swap(cur_min, cur_max);
            cur_min = min(nums[i], cur_min * nums[i]);
            cur_max = max(nums[i], cur_max * nums[i]);
            ans = max(ans, cur_max);
        }
        return ans;
    }
};

Preparing for an interview? Check out this!

Join my Email List for more insights, It's Free!😋

← 5 things I learned from Tesla's ... Intersection of Two Linked Lists →