题目：Find the contiguous subarray within an array (containing at least one number) which has the largest product.
一.暴力破解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class {
public int maxProduct(int[] nums) {
int n=nums.length;
int ans=-2147483648;
for(int i=0;i<n;i++)
{
for(int last=i;last<n;last++)
{
int product=1;
for(int j=i;j<=last;j++)
{
product*=nums[j];
if(product>ans)
{
ans=product;
}
}
}
}
return ans;
}
}
|
二、优化枚举
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class {
public int maxProduct(int[] nums) {
int n=nums.length;
int ans=-2147483648;
for(int i=0;i<n;i++)
{
int product=1;
for(int last=i;last<n;last++)
{
product*=nums[last];
if(product>ans)
{
ans=product;
}
}
}
return ans;
}
}
|
三、时间复杂度为O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class {
public int maxProduct(int[] nums) {
int maxProduct=nums[0];
int minProduct=nums[0];
int Product=nums[0];
int n=nums.length;
for(int i=1;i<n;i++)
{
int temp=maxProduct;
maxProduct=Math.max(Math.max(maxProduct*nums[i],minProduct*nums[i]),nums[i]);
minProduct=Math.min(Math.min(temp*nums[i],minProduct*nums[i]),nums[i]);
if(maxProduct>Product)
{
Product=maxProduct;
}
}
return Product;
}
}
|
近期评论