题目描述

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32 位整数。
子数组是数组的连续子序列。

输入输出样例

示例 1

输入

nums = [2,3,-2,4]

输出

解释

子数组 [2,3] 有最大乘积 6。

示例 2

输入

nums = [-2,0,-1]

输出

解释

结果不能为 2, 因为 [-2,-1] 不是子数组。

提示

1 ≤ nums.length ≤ 2 × 10^4
-10 ≤ nums[i] ≤ 10
nums 的任何前缀或后缀的乘积都保证是一个 32 位整数。

题解

考虑当前位置的元素 nums[i]。如果 nums[i] 是一个负数的话，那么我们希望以它前一个位置结尾的某个子数组的积也是负数，这样就可以负负得正，并且我们希望这个积尽可能负得更多，即尽可能小。如果当前位置是一个正数的话，我们更希望以它前一个位置结尾的某个子数组的积也是个正数，并且希望它尽可能大。

#define MAX(a, b) (((a) > (b)) ? (a) : (b))
#define MIN(a, b) (((a) < (b)) ? (a) : (b))

int maxProduct(int* nums, int numsSize){
    int maxProduct = 1, minProduct = 1, maxMaxProduct = *nums, tmp, i;
    for (i = 0; i < numsSize; i++) {
        if (nums[i] < 0) {
            tmp = maxProduct;
            maxProduct = minProduct;
            minProduct = tmp;
        } // 如果 nums[i] 为负数，最大积就变成最小积，最小积就变成最大积

        maxProduct = MAX(nums[i], nums[i] * maxProduct);
        minProduct = MIN(nums[i], nums[i] * minProduct);
        maxMaxProduct = MAX(maxProduct, maxMaxProduct);
    }
    return maxMaxProduct;
}

参考题解：