Sunday, September 20, 2015

LeetCode OJ - Maximum Product Subarray

Problem:

Please find the problem here.

Solution:

It is natural for us to proceed to this problem, it has a solution that is very similar with the last one, with one catch. Negative times negative give positive, so we cannot keep track of only one best, but two.

The code is tricky with respect to the negative case. As you can see, the code try to compute the best possible product of positive products only. A tricky case is for a sequence of only negative products. In that case, the code will not output the correct answer?

No - the code will still output the correct answer - this happen because the ONLY case where a sequence ONLY have negative product is the case where you have only one element, and that case is well handled by setting the best_product to nums[0] to begin with ... see, now that's tricky.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/maximum-product-subarray/

#include "LEET_MAXIMUM_PRODUCT_SUBARRAY.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

namespace _LEET_MAXIMUM_PRODUCT_SUBARRAY
{
    class Solution
    {
    public:
        int maxProduct(vector<int>& nums)
        {
            int size = nums.size();
            if (size == 0)
            {
                return 1;
            }
            int best_product = nums[0];
            int best_positive_ends = nums[0];
            int best_negative_ends = nums[0];
            if (nums[0] > 0)
            {
                best_negative_ends = 0;
            }
            if (nums[0] < 0)
            {
                best_positive_ends = 0;
            }
            for (int i = 1; i < size; i++)
            {
                int new_best_positive_ends = 0;
                int new_best_negative_ends = 0;
                if (nums[i] == 0)
                {
                    best_positive_ends = best_negative_ends = 0;
                }
                else if (nums[i] > 0)
                {
                    if (best_positive_ends != 0)
                    {
                        new_best_positive_ends = best_positive_ends * nums[i];
                    }
                    else
                    {
                        new_best_positive_ends = nums[i];
                    }
                    if (best_negative_ends != 0)
                    {
                        new_best_negative_ends = best_negative_ends * nums[i];
                    }
                    else
                    {
                        new_best_negative_ends = 0;
                    }
                }
                else if (nums[i] < 0)
                {
                    if (best_positive_ends != 0)
                    {
                        new_best_negative_ends = best_positive_ends * nums[i];
                    }
                    else
                    {
                        new_best_negative_ends = nums[i];
                    }
                    if (best_negative_ends != 0)
                    {
                        new_best_positive_ends = best_negative_ends * nums[i];
                    }
                    else
                    {
                        new_best_positive_ends = 0;
                    }
                }

                best_positive_ends = new_best_positive_ends;
                best_negative_ends = new_best_negative_ends;
                best_product = max(best_product, best_positive_ends);
            }

            return best_product;
        }
    };
};

using namespace _LEET_MAXIMUM_PRODUCT_SUBARRAY;

int LEET_MAXIMUM_PRODUCT_SUBARRAY()
{
    int case1[] = { -1 };
    Solution s;
    cout << s.maxProduct(vector<int>(case1, case1 + _countof(case1))) << endl;
    return 0;
}

No comments :

Post a Comment