题解 | #连续子数组的最大乘积#

#include <algorithm>
#include <climits>
#include <deque>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @return int整型
     */
    int maxProduct(vector<int>& nums) {
        // write code here
        if (nums.size() == 1) {
            return nums[0];
        }
        vector<int>path;
        vector<vector<int>>nonezero_nums_vec;
        int result = INT_MIN;
	  //将数组从左到右切片，确保每一个切片都不含0且连续
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 0) {
                nonezero_nums_vec.push_back(path);
                result = 0;
                path.clear();
                continue;
            } else {
                if (i == nums.size() - 1) {
                    path.push_back(nums[i]);
                    nonezero_nums_vec.push_back(path);
                } else {
                    path.push_back(nums[i]);
                }
            }
        }
        for (int i = 0; i < nonezero_nums_vec.size(); i++) {
            int temp = compute_nonzero_nums(nonezero_nums_vec[i]);
            result = max(result, temp );
        }
        return result;

    }
  //计算不含0数组中的最大乘积数组的乘积
    int compute_nonzero_nums(vector<int>& nonezero_nums) {
        if (nonezero_nums.size() == 0) {
            return 0;
        }
        else if (nonezero_nums.size()==1) {
            return nonezero_nums[0];
        }
        int result = 1;
        for (int i = 0; i < nonezero_nums.size(); i++) {
            result = result * nonezero_nums[i];
        }
        if (result > 0) {
            return result;
        } else {
            int left_first_negative_position = 0;
            int right_first_negative_position = nonezero_nums.size() - 1;
            for (int i = 0; i < nonezero_nums.size(); i++) {
                if (nonezero_nums[i] < 0) {
                    left_first_negative_position = i;
                    break;
                }
            }
            for (int j = nonezero_nums.size() - 1; j >= 0; j--) {
                if (nonezero_nums[j] < 0) {
                    right_first_negative_position = j;
                    break;
                }
            }
            int temp1 = 1;
            for (int i = left_first_negative_position + 1; i < nonezero_nums.size(); i++) {
                temp1 =  temp1 * nonezero_nums[i];
            }
            int temp2 = 1;
            for (int i = right_first_negative_position - 1; i >= 0; i--) {
                temp2 =  temp2 * nonezero_nums[i];
            }
            result = max(temp1, temp2);
        }
        return result;
    }
};