152.乘积最大子数组 梦里梦外; 2021-06-22 15:38 372阅读 0赞 //给你一个整数数组 nums ,请你找出数组中乘积最大的连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。 // // 示例 1: // 输入: \[2,3,-2,4\] //输出: 6 //解释: 子数组 \[2,3\] 有最大乘积 6。 // // 示例 2: // 输入: \[-2,0,-1\] //输出: 0 //解释: 结果不能为 2, 因为 \[-2,-1\] 不是子数组。 // Related Topics 数组 动态规划 * 思路1:暴力求解,递归 * 思路2:动态规划 class Solution { public int maxProduct(int[] nums) { int max = Integer.MIN_VALUE, imax = 1, imin = 1; //一个保存最大的,一个保存最小的。 for(int i=0; i<nums.length; i++){ if(nums[i] < 0){ //如果数组的数是负数,那么会导致最大的变最小的,最小的变最大的。因此交换两个的值。 int tmp = imax; imax = imin; imin = tmp; } imax = Math.max(imax*nums[i], nums[i]); imin = Math.min(imin*nums[i], nums[i]); max = Math.max(max, imax); } return max; } }
还没有评论,来说两句吧...