题目描述
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
题解
最容易想到的还是暴力：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| int maxProduct(vector<int>& nums) {
int size=nums.size();
int max=nums[0];
for(int i=size-1;i>=0;i--)
{
int mul=nums[i];
int m=mul;
for(int j=i-1;j>=0;j--)
{
mul*=nums[j];
m=mul>m?mul:m;
}
max=m>max?m:max;
}
return max;
}
|
时间复杂度：O($n^2$)，效率肯定高不了：
执行用时：436 ms, 在所有 C++ 提交中击败了5.51%的用户
内存消耗：11.7 MB, 在所有 C++ 提交中击败了6.25%的用户
aha，似乎动态规划的思路是没有错的，只是现在由于存在负数，所以需要维护max和min，当遇到负数时，max和min就互换了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| int maxProduct(vector<int>& nums) {
int size=nums.size();
int m1=nums[0],m2=nums[0];
int ans=m1;
for(int i=1;i<size;i++)
{
if(nums[i]>0)
{
m1=max(m1*nums[i],nums[i]);
m2=min(m2*nums[i],nums[i]);
ans=max(ans,m1);
}
else if(nums[i]==0)
{
m1=0;m2=0;
ans=max(ans,0);
}
else
{
int t=m1;
m1=max(m2*nums[i],nums[i]);
m2=min(t*nums[i],nums[i]);
ans=max(ans,m1);
}
}
return ans;
}
|
时间复杂度：O(n)
执行用时：8 ms, 在所有 C++ 提交中击败了77.75%的用户
内存消耗：12 MB, 在所有 C++ 提交中击败了6.25%的用户
可是，没有意义了啊。最好的时机都没有抓住呢。
TODO：数据库概念学习