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 | class Solution {
int max3(int x, int y, int z) {
return max(max(x, y), z);
}
int min3(int x, int y, int z) {
return min(min(x, y), z);
}
public:
int maxProduct(vector<int>& nums) {
constexpr int SIZE = 20001;
int maxP[SIZE];
int minP[SIZE];
int ans = nums[0];
maxP[0] = nums[0];
minP[0] = nums[0];
for (int i = 1; i < nums.size(); i++) {
maxP[i] = max3(nums[i], nums[i] * maxP[i - 1], nums[i] * minP[i - 1]);
minP[i] = min3(nums[i], nums[i] * maxP[i - 1], nums[i] * minP[i - 1]);
ans = max(ans, maxP[i]);
}
return ans;
}
};
|