JAVA练习273-乘积最大子数组

题目概览给你一个整数数组nums请你找出数组中乘积最大的非空连续 子数组该子数组中至少包含一个数字并返回该子数组所对应的乘积。测试用例的答案是一个32-位整数。请注意一个只包含一个元素的数组的乘积是这个元素的值示例 1:输入:nums [2,3,-2,4]输出:6解释:子数组 [2,3] 有最大乘积 6。示例 2:输入:nums [-2,0,-1]输出:0解释:结果不能为 2, 因为 [-2,-1] 不是子数组。提示:1 nums.length 2 * 104-10 nums[i] 10nums的任何子数组的乘积都保证是一个32-位整数来源152. 乘积最大子数组 - 力扣LeetCode解题分析方法动态规划因为含有负数的情况的所以要把 负数乘积 * 负数的情况考虑进去因此不但需要得到最大乘积也要得到最小乘积。令当前索引为 i最大乘积数组为 dp那么 dp[ i ] 如果是最大乘积乘积一定是 nums[ i ] * dp [ n - 1]如果不是最大乘积就是 nums[i] 自己。考虑到负数情况令最大乘积为 max最小乘积为 min可以得到状态转移方程max [ n ] max { max[ n - 1 ] * n, min [ n - 1 ] * n, n }min [ n ] min { max[ n - 1 ] * n, min [ n - 1 ] * n, n }时间复杂度O(n)空间复杂度O(n)class Solution { public int maxProduct(int[] nums) { int[] min new int[nums.length1]; min[0] nums[0]; int[] max new int[nums.length1]; max[0] nums[0]; int result nums[0]; for (int i 1; i nums.length; i) { min[i] Math.min(Math.min(max[i-1] * nums[i], min[i-1] * nums[i]), nums[i]); max[i] Math.max(Math.max(max[i-1] * nums[i], min[i-1] * nums[i]), nums[i]); result Math.max(max[i], result); } return result; } }