package dp.maxProduct; /** * 152. 乘积最大子数组 * 给你一个整数数组 nums ,请你找出数组中乘积最大的连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。 * <p> * <p> * <p> * 示例 1: * <p> * 输入: [2,3,-2,4] * 输出: 6 * 解释: 子数组 [2,3] 有最大乘积 6。 * 示例 2: * <p> * 输入: [-2,0,-1] * 输出: 0 * 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。 */ public class maxProduct { //由于可能出现负数,导致最大值,最小值的交替,所以要维护俩个值 public static int maxProduct(int[] nums) { if (nums.length == 0) { return 0; } int imax = 1; int imin = 1; int res = Integer.MIN_VALUE; for (int i = 0; i < nums.length; i++) { if (nums[i] < 0) { int temp = imax; imax = imin; imin = temp; } imax = Math.max(nums[i], nums[i] * imax); imin = Math.min(nums[i], nums[i] * imin); res = Math.max(res, imax); } return res; } public static void main(String[] args) { int[] nums = {2, 3, -2, 4}; System.out.println(maxProduct(nums)); } }
不会,我可以学;落后,我可以追赶;跌倒,我可以站起来!