152. 乘积最大子数组
约 194 字
预计阅读 1 分钟
f[i]以第i个数字结尾的乘积最大的子数组，与和最大的子数组不同，乘积最大的子数组由两部分转移而来。nums[i - 1] < 0, $f[i] = max(fmin[i - 1] * nums[i - 1], nums[i - 1])$nums[i - 1] > 0,$f[i] = max(fmax[i - 1] * nums[i - 1], nums[i - 1])$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
int maxProduct(vector<int>& nums) {
int n = nums.size();
vector<int> fmax(n + 1, 0);
vector<int> fmin(n + 1, 0);
fmax[0] = 1;
fmin[0] = 1;
for (int i = 1; i <= n; i++) {
fmax[i] = max(nums[i - 1],
max(fmax[i - 1] * nums[i - 1], fmin[i - 1] * nums[i - 1]));
fmin[i] = min(nums[i - 1],
min(fmax[i - 1] * nums[i - 1], fmin[i - 1] * nums[i - 1]));
}
return *max_element(fmax.begin() + 1, fmax.end());
}
};
|