Easy to understand C++ solution,3ms


  • 0
    class Solution {
    public:
    	int maxProduct(vector<int>& nums) {
    		if (nums.size() == 1) return nums[0];
    		int last_zero = -1;
    		int max_res = 0;
    		for (int i = 0; i < nums.size(); i++) {
    			if (nums[i] == 0) {
    				max_res = max(max_res, _max(nums, last_zero + 1, i - 1));
    				last_zero = i;
    			}
    		}
    		if (last_zero > -1) max_res = max(max_res, _max(nums, last_zero + 1, nums.size() - 1));
    		if (find(nums.begin(), nums.end(), 0) != nums.end()) {
    			return max_res;
    		}
    		return _max(nums, 0, nums.size() - 1);
    	}
    
    	int _max(vector<int>& nums, int start, int end)
    	{
    		if (start > end) return 0;
    		int first = -1, last = -1, n = nums.size();
    		int sum = _getProduct(nums, start, end);
    		if (sum > 0) return sum;
    		for (int i = start; i <= end; ++i) {
    			if (nums[i] < 0) {
    				first = i;
    				break;
    			}
    		}
    		for (int i = end; i >= start; --i) {
    			if (nums[i] < 0) {
    				last = i;
    				break;
    			}
    		}
    		if (first == last) {
    			return max(_getProduct(nums, start, first - 1), _getProduct(nums, last + 1, end));
    		}
    		else {
    			int tmp = max(_getProduct(nums, start, last - 1), _getProduct(nums, first + 1, end));
    			return tmp;
    		}
    	}
    
    	int _getProduct(vector<int>& nums, int start, int end) {
    		if (start > end) return 0;
    		int sum = 1;
    		for (int i = start; i <= end; i++) {
    			sum *= nums[i];
    		}
    		return sum;
    	}
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.