leetcode152.乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。测试用例的答案是一个 32-位 整数。
示例 1:
输入: nums = [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: nums = [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
思路： 注意这道题涉及到符号问题 ；dp[i]表示以nums[i]结尾的子数组的最大乘积；通过这道题发现更新最大值时用if比用Math.max方法更节省时间复杂度
public int maxProduct(int[] nums) {
int[] dp=new int [nums.length];
int max=nums[0];
for(int i=0;i<nums.length;i++){
dp[i]=nums[i];
int temp=nums[i];//temp记录子数组乘积
//得到以num[i]结尾的所有子数组乘积情况，取其中最大作为dp[i]
for(int j=i-1;j>=0;j--){
temp*=nums[j];
// 比较神奇的是这里用Math.max代替就会超时，因此如果为了节省时间复杂度还是用if语句吧
if(temp>dp[i])
dp[i]=temp;
}
if(dp[i]>max)
max=dp[i];
}
return max;
}原文地址：https://blog.csdn.net/m0_64995001/article/details/145243153
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！