leetcode 152.乘积最大子数组

题目

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

题解

对于一个数组的累乘，我们会发现以下规律： 1、正数越多，累乘值必然越大； 2、若出现负值，则当前值若为正值，累乘后会变成最小值；当前值若为负值，则会转化为最大值； 3、若当前值为0，无论累乘多少值，都为0，因此，若读取到0，则保存当前状态最大值，重新进行累乘计算；

程序设计

由于正值越多，累乘值越大；负值会使得数据产生突变，由负值变成正值，正值变成负值；0会使得累乘值归零。因此，我们设置res来保存当前最大累乘值，设置max来保存当前最大值，设置min来保存前序累乘值遇见负数时突变的情况；

public int maxProduct(int[] nums) { int res = nums[0]; int max = 1; int min = 1; for (int num : nums) { // 若小于0，则互换max与min的值 if (num < 0) { int temp = min; min = max; max = temp; } // 主要累乘值 max = Math.max(max * num, num); // 负数保存值 min = Math.min(min * num, num); // 结果值 res = Math.max(max, res); } return res; }

代码解析

1、遇见正数会逐步累乘至max上； 2、遇见负数则会互换max与min的位置，使得min记录下之前的max值，防止再次遇见负数进行突变；max换为min的值，会因为Math.max(max*num, num)的语句覆盖原本的数值从而从新开始； 3、遇见0，则会全部归零，并重新开始。

调试函数：

public static void main(String[] args) { int[] nums = {2, 2, 3, -1, 2, 2, 3, 4}; MaxProduct M = new MaxProduct(); int r = M.maxProduct(nums); System.out.println(r); }