珠海城乡建设厅网站,台州城乡建设规划网站,云服务器如何搭建,视频网站开发工程师题目描述#xff1a;思路#xff1a;对于每个位置 i#xff0c;我们要计算以 nums[i] 为结尾的子数组的最大乘积和最小乘积。最大乘积#xff1a;最大乘积子数组可以通过前面的最大乘积或者最小乘积来扩展#xff0c;尤其是当数组中有负数时#xff0c;最小乘积可能会与负…题目描述思路对于每个位置i我们要计算以nums[i]为结尾的子数组的最大乘积和最小乘积。最大乘积最大乘积子数组可以通过前面的最大乘积或者最小乘积来扩展尤其是当数组中有负数时最小乘积可能会与负数相乘变成最大的乘积。最小乘积最小乘积子数组同样可以通过前面的最大乘积或者最小乘积来扩展尤其是负数的情况下。为了在每一步都记录最大乘积和最小乘积我们使用两个数组fmax和fminfmax[i]表示以nums[i]为结尾的最大乘积。fmin[i]表示以nums[i]为结尾的最小乘积。状态转移方程对于fmax[i]fmax[i] max(fmax[i-1] * nums[i], fmin[i-1] * nums[i], nums[i])fmax[i-1] * nums[i]将前面的最大值乘上当前元素。fmin[i-1] * nums[i]将前面的最小值乘上当前元素负负得正可能会变成最大值。nums[i]单独作为一个新的子数组。对于fmin[i]fmin[i] min(fmax[i-1] * nums[i], fmin[i-1] * nums[i], nums[i])fmax[i-1] * nums[i]将前面的最大值乘上当前元素可能会变成最小值。fmin[i-1] * nums[i]将前面的最小值乘上当前元素可能会变成最小值。nums[i]单独作为一个新的子数组。最终结果在每一步的fmax[i]记录了以nums[i]为结尾的最大乘积我们最后只需要返回fmax数组中的最大值即可。代码class Solution { public int maxProduct(int[] nums) { int n nums.length; int[] fmax new int[n]; // 存储到当前位置的最大乘积 int[] fmin new int[n]; // 存储到当前位置的最小乘积 fmax[0] fmin[0] nums[0]; // 初始化第一个元素 // 从第二个元素开始计算 for (int i 1; i n; i) { int x nums[i]; // 计算当前位置的最大和最小乘积 fmax[i] Math.max(Math.max(fmax[i-1] * x, fmin[i-1] * x), x); fmin[i] Math.min(Math.min(fmax[i-1] * x, fmin[i-1] * x), x); } // 返回 fmax 数组中的最大值即最大乘积 return Arrays.stream(fmax).max().getAsInt(); } }代码解释初始化fmax[0] fmin[0] nums[0]初始化第一个元素的最大乘积和最小乘积为nums[0]。动态规划计算从i 1开始遍历整个数组对于每个元素nums[i]根据状态转移方程计算fmax[i]和fmin[i]。fmax[i]通过比较前一个元素的最大乘积和最小乘积乘以当前元素或者仅仅是当前元素本身得到当前位置的最大乘积。fmin[i]通过同样的方式得到当前位置的最小乘积。返回最大值Arrays.stream(fmax).max().getAsInt()计算fmax数组中的最大值返回整个数组的最大乘积。