Maximum Product Subarray

Description

Example

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

class Solution {
public:
    /**
     * @param nums: a vector of integers
     * @return: an integer
     */
    int maxProduct(vector<int>& nums) {
        // write your code here
        if (nums.empty()) {
            return 0;
        }
        int result = nums[0];
        int len = nums.size();
        vector<int> maxval(len);
        vector<int> minval(len);
        maxval[0] = nums[0];
        minval[0] = nums[0];
        for (int i = 1; i < len ; ++i) {
            maxval[i] = nums[i];
            minval[i] = nums[i];
            // for just one, only [0] is needed.
            // if (i == 0) {
            //     result = max(result, maxval[i]);
            //     continue;
            // }
            if (nums[i] > 0) {
                maxval[i] = max(maxval[i-1] * nums[i], maxval[i]);
                minval[i] = min(minval[i-1] * nums[i], minval[i]);
            } else if (nums[i] < 0) {
                maxval[i] = max(minval[i-1] * nums[i], maxval[i]);
                minval[i] = min(maxval[i-1] * nums[i], minval[i]);
            }
            result = max(result, maxval[i]);
        }
        return result;
    }
};

Similar problems

x

Tags

x