做网站给客户聊天记录/黄页网站推广效果
- 乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
此题与求最大连续和相似
1.暴力方法
class Solution {public int maxProduct(int[] nums) {int len = nums.length;if(len == 0) return 0;//暴力方法int ans = Integer.MIN_VALUE;for(int i = 0; i < len; i++){int tmp = 1;for(int j = i; j < len; j++){tmp *= nums[j];ans = Math.max(ans, tmp);}}return ans;}
}
2。老方法就会出现问题
因为这个并不满足局部最优的，存在负数，比如负负得正，这种情况是判断不出来的
由于存在负数，那么会导致最大的变最小的，最小的变最大的。因此还需要维护当前最小值min
实际上这个只需要用一个变量来记录即可
class Solution {public int maxProduct(int[] nums) {int len = nums.length;if(len == 0) return 0;//暴力方法int ans = nums[0];int[] dp = new int[len];dp[0] = nums[0];for(int i = 1; i < len; i++){dp[i] = Math.max(dp[i - 1] * nums[i], nums[i]);ans = Math.max(ans, dp[i]);}return ans;}
}
修正
class Solution {public int maxProduct(int[] nums) {int len = nums.length;if(len == 0) return 0;int ans = Integer.MIN_VALUE;int max = 1, min = 1;//同时记录最大值，最小值，互换for(int i = 0; i < len; i++){if(nums[i] < 0) {//互换max， minif(nums[i] < 0){int tmp = max;max= min;min = tmp;}}max = Math.max(max* nums[i], nums[i]);min = Math.min(min* nums[i], nums[i]);ans = Math.max(ans, max);}return ans;}
}