Given an integer array nums
, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example 1:
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
题目大意:找到一个连续的字数粗,使他们的乘积为最大值,返回这个最大值
思路:注意这里,要维护一个最大值和最小值,因为最小值可能为负数,我们知道,负负得正;
public int maxProduct(int[] nums) {
if (nums==null||nums.length ==0) return 0;
int max = nums[0],min = nums[0],result = nums[0];
for (int i=1;i<nums.length;i++){
int temp = max;
max = Math.max(Math.max(nums[i]*max,nums[i]*min),nums[i]) ;
min = Math.min(Math.min(nums[i]*temp,nums[i]*min),nums[i]);
if (result<max) result = max;
}
return result;
}
Given an integer array, find three numbers whose product is maximum and output the maximum product.
Example 1:
Input: [1,2,3]
Output: 6
Example 2:
Input: [1,2,3,4]
Output: 24
Note:
题目大意:在一个数组中找三个数,使得这三个数的乘积最大;
这个题目与LeetCode152有相似之处,由于题目没有说明是非负数,所以一定要负数考虑在范围内;
这个思路来自于,从一个数组中查找到第二大的值。我们采用同样的方法,得到数组中的第一大,第二大,第三大的数。
public int maximumProduct(int[] nums) {
int firstMax = Integer.MIN_VALUE;
int secMax = firstMax,thirdMax = firstMax;
int firstMin = Integer.MAX_VALUE;
int secMin = firstMin;
for (int i =0;i<nums.length;i++){
if (nums[i]>firstMax){
thirdMax = secMax;
secMax = firstMax;
firstMax = nums[i];
}else {
if (nums[i]>secMax){
thirdMax = secMax;
secMax = nums[i];
}else {
if (nums[i]>thirdMax){
thirdMax = nums[i];
}
}
}
if (nums[i]<firstMin){
secMin = firstMin;
firstMin = nums[i];
}else {
if (nums[i]<secMin){
secMin = nums[i];
}
}
}
return Math.max(firstMax*secMax*thirdMax,firstMax*firstMin*secMin);
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。