大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。
一、题目
1、算法题目
“给定一个整数数组，找出数组中乘积最大的非空连续子数组，并返回该子数组所对应的乘积。”
2、题目描述
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
子数组 是数组的连续子序列。
示例 1： 输入: nums = [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。
示例 2： 输入: nums = [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
二、解题
1、思路分析
遇到这种枚举所有答案的问题，就可以考虑一下是否可以使用动态规划。
这道题的题意是要求遍历数组计算乘积最大的值。
那么就维护一个最大值：
imax = max(imax * nums[i] , nums[i])
由于存在负数，将最大的变最小的，最小的变最大的，因此还需要维护一个最小值：
imin = min(imin * nums[i] , nums[i])
当负数出现则imax与imin进行交换再进行下一步计算。
2、代码实现
代码参考：
class Solution { public int maxProduct(int[] nums) { int maxF = nums[0], minF = nums[0], ans = nums[0]; int length = nums.length; for (int i = 1; i < length; ++i) { int mx = maxF, mn = minF; maxF = Math.max(mx * nums[i], Math.max(nums[i], mn * nums[i])); minF = Math.min(mn * nums[i], Math.min(nums[i], mx * nums[i])); ans = Math.max(maxF, ans); } return ans; } }
3、时间复杂度
时间复杂度：O(n)
其中n是数组的长度，遍历了数组，时间复杂度为O(n)。
空间复杂度：O(1)
只需要常量级的空间储存变量。
三、总结
这道题就是求数组中子区间的最大乘积。
对于乘法，负负得正，所以对于这道题要维护两个变量，一个最大值一个最小值。
最小值可能为负数，负数乘负数，当前的最大值就变成最小值，最小值就变成最大值了。
